一、dfs框架：
vector<int>G[maxn]; //存图
int vis[maxn]; //节点访问标记
void dfs(int u)
{
vis[u] = ;
PREVISIT(u); //访问节点u之前的操作
int d = G[u].size();
for(int i = ; i < d; i++)//枚举每条边
{
int v = G[u][i];
if(!vis[v])dfs(v);
}
POSTVISIT(u); //访问节点u之后的操作
}
二、无向图连通分量
void find_cc()
{
current_cc = ;//全局变量 连通块编号
memset(vis, , sizeof(vis));
for(int u = ; u < n; u++)if(!vis[u])//依次检查每个节点，如果未访问过，说明它属于一个新的连通分量，从该点dfs访问整个连通分量
{
current_cc++;
dfs(u);
}
}
三、二分图判定
调用之前，清空color数组，调用之前，先给color[u]赋值1
int color[maxn];//0表示未染色 1表示白色 2表示黑色
bool bipartite(int u)
{
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if(color[u] == color[v])return false;//u v颜色一样
if(!color[v])
{
color[v] = - color[u];//节点u与v染不同的颜色
if(!bipartite(v))return false;
}
}
return true;
}
四、无向图的割点和桥
加入时间戳
int dfs_clock;
void PREVISIT(int u){pre[u] = ++dfs_clock;}
void POSTVISIT(int u){post[u] = ++dfs_clock;}
注意：求桥的时候注意重边
求割点和桥可以用下面求双连通分量的代码
五、无向图的双连通分量
点-双连通分量
struct Edge
{
int u, v;
Edge(){}
Edge(int u, int v):u(u), v(v){}
};
int pre[maxn];//时间戳数组
int iscut[maxn];//割点
int bccno[maxn];//点-双连通分量编号 （割点的编号没有意义）
int dfs_clock, bcc_cnt;//时间戳 双连通分量编号
vector<int>G[maxn], bcc[maxn];//G存储图 bcc存储每个双连通分量的点
stack<Edge>S; int dfs(int u, int fa)
{
int lowu = pre[u] = ++dfs_clock;
int child = ;
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
Edge e(u, v);
if(!pre[v])
{
S.push(e);
child++;
int lowv = dfs(v, u);
lowu = Min(lowu, lowv);
if(lowv >= pre[u])
{
iscut[u] = ;
bcc_cnt++;
bcc[bcc_cnt].clear();
for(;;)
{
Edge x = S.top();
S.pop();
if(bccno[x.u] != bcc_cnt){bcc[bcc_cnt].push_back(x.u);bccno[x.u] = bcc_cnt;}
if(bccno[x.v] != bcc_cnt){bcc[bcc_cnt].push_back(x.v);bccno[x.v] = bcc_cnt;}
if(x.u == u && x.v == v)break;
}
}
}
else if(pre[v] < pre[u] && v != fa)
{
S.push(e);
lowu = Min(lowu, pre[v]);
}
}
if(fa < && child == )iscut[u] = ;
return lowu;
}
void find_bcc(int n)//求解点-双连通分量
{
Mem(pre);
Mem(iscut);
Mem(bccno);
dfs_clock = bcc_cnt = ;
for(int i = ; i < n; i++)if(!pre[i])dfs(i, -);
}
边-双连通分量
struct Edge
{
int u, v;
Edge(){}
Edge(int u, int v):u(u), v(v){}
};
int pre[maxn];//时间戳数组
int isbridge[maxm];//桥
int bccno[maxn];//边-双连通分量编号 （任意两个无交集）
int low[maxn];//low[u]为u后代可以返回的最早祖先值
int dfs_clock, bcc_cnt;//时间戳 双连通分量编号
vector<Edge>e;//存边
vector<int>G[maxn], bcc[maxn];//G存储图 bcc存储每个双连通分量的点
//G存边在e中的下标
void init(int n)
{
for(int i = ; i < n; i++)G[i].clear();
e.clear();
}
void addedge(int u, int v)//双向边
{
e.push_back(Edge(u, v));
G[u].push_back(e.size() - );
e.push_back(Edge(v, u));
G[v].push_back(e.size() - );//正好满足双向边^操作
}
void dfs1(int u, int fa)//找出所有的桥
{
low[u] = pre[u] = ++dfs_clock;
for(int i = ; i < G[u].size(); i++)
{
int v = e[G[u][i]].v;
if(!pre[v])
{
dfs1(v, u);
low[u] = Min(low[u], low[v]);
if(low[v] > pre[u])//是桥，双向边均标记一下
{
isbridge[G[u][i]] = isbridge[G[u][i]^] = ;
}
}
else if(pre[v] < pre[u] && v != fa)
{
low[u] = Min(low[u], pre[v]);
}
}
}
void dfs2(int u)//dfs染色找边-双连通分量即可
{
pre[u] = ;//vis数组标记
bccno[u] = bcc_cnt;
bcc[bcc_cnt].push_back(u);
for(int i = ; i < G[u].size(); i++)
{
int v = e[G[u][i]].v;
if(isbridge[G[u][i]])continue;//不走桥
if(!pre[v])dfs2(v);
}
}
void find_bcc(int n)//求解边-双连通分量
{
Mem(pre);Mem(isbridge);Mem(bccno);Mem(low);
dfs_clock = bcc_cnt = ;
for(int i = ; i < n; i++)if(!pre[i])dfs1(i, -);
Mem(pre);
for(int i = ; i < n; i++)if(!pre[i]){bcc_cnt++; bcc[bcc_cnt].clear(); dfs2(i);}
}
六、有向图的强连通分量
vector<int>G[maxn];
int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack<int>S;
void dfs(int u)
{
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u);
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if(!pre[v])
{
dfs(v);
lowlink[u] = Min(lowlink[u], lowlink[v]);
}
else if(!sccno[v])
{
lowlink[u] = Min(lowlink[u], pre[v]);
}
}
if(lowlink[u] == pre[u])
{
scc_cnt++;
for(;;)
{
int x = S.top();
S.pop();
sccno[x] = scc_cnt;
if(x == u)break;
}
}
}
void find_scc(int n)
{
dfs_clock = scc_cnt = ;
Mem(sccno);
Mem(pre);
for(int i = ; i < n; i++)if(!pre[i])dfs(i);
}
七、2-SAT问题
struct TwoSAT
{
int n;
vector<int>G[maxn * ];
bool mark[maxn * ];
int S[maxn * ], c;
bool dfs(int x)
{
if(mark[x^])return false;
if(mark[x])return true;
mark[x] = true;
S[c++] = x;
for(int i = ; i < G[x].size(); i++)
if(!dfs(G[x][i]))return false;
return true;
}
void init(int n)
{
this->n = n;
for(int i = ; i < n * ; i++)G[i].clear();
Mem(mark);
}
//x = xval or y = yval
void add_clause(int x, int xval, int y, int yval)
{
x = x * + xval;
y = y * + yval;
G[x ^ ].push_back(y);
G[y ^ ].push_back(x);
}
bool solve()
{
for(int i = ; i < n * ; i += )
{
if(!mark[i] && !mark[i + ])
{
c = ;
if(!dfs(i))
{
while(c > )mark[S[--c]] = false;
if(!dfs(i + ))return false;
}
}
}
return true;
}
};