相关概念
强连通：对于结点 $u$、$v$，同时存在 $u$ 到 $v$ 的路径和 $v$ 到 $u$ 的路径。
强连通图：图中任意两个结点都强连通。
强连通分量：有向非强连通图中的极大强连通子图
两种求法
Kosaraju算法
算法原理
根据定义，对于一个结点 $A$，我们搜索 $A$ 能到达的所有结点；我们再搜索能达到 $A$ 的所有结点。二者的交集显然是包含 $A$ 的强连通分量。
一些细节
反向建边。
我们希望一次搜索就能找到所有强连通分量。考虑在第一次搜索中，在某个结点其中一个儿子子树中的结点不可能与原结点另一个儿子子树中的结点构成强连通分量。因此我们在第二次搜索中要杜绝这种情况的出现。
在第一次搜索中，我们存下每个结点结束访问的时间戳。第二次搜索时，按照第一次搜索的时间戳倒序搜索，这样可以保证从 $A$ 搜到的都在包含 $A$ 的强连通分量中。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| void dfs1(int u){
fl[u]=1;
for(int i=lst[u];i;i=e[i].lst){
int v=e[i].t;
if(fl[v])continue;
dfs1(v);
}
xu[++cmt]=u;
}
void dfs2(int u,int f){
if(find(u)!=find(f)){
sz[find(f)]+=sz[find(u)];
fa[find(u)]=find(f);
}
fl[u]=1;
for(int i=lstf[u];i;i=fe[i].lst){
int v=fe[i].t;
if(fl[v])continue;
dfs2(v,f);
}
}
void kosaraju(){
for(int i=1;i<=n;i++){
if(!fl[i])dfs1(i);
}
memset(fl,0,sizeof(fl));
for(int i=n;i>=1;i--){
if(!fl[xu[i]])dfs2(xu[i],xu[i]);
}
}
|
复杂度
由于进行了两次DFS，所以总复杂度为 $O(2\times E)$。
Tarjan算法
一些概念
回边：连向栈中的边（栈呢？等一下嘛）
时间戳：搜索到某一结点的序
最老祖先：某一结点及其子树中，能到达的最远的祖先。
算法原理
搜索，对于每个结点，先入栈，然后递归更新所有儿子结点。枚举该点的所有出边，如果连向儿子结点，用儿子结点的最老祖先更新该结点的最老祖先；如果出边是回边，直接更新最老祖先。更新结束后，如果该点的最老祖先不是自己，说明该点处在某一强连通分量中，返回，不出栈。如果是自己，则退栈直到自己，退出的这部分结点属于一个强连通分量。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| void dfs(int u,int fa){
dfn[u]=low[u]=++tim;
stk[++top]=u;
fl[u]=zh[u]=1;
for(int i=lst[u];i;i=e[i].lst){
int v=e[i].t;
if(!fl[v]){
dfs(v,u);
low[u]=min(low[u],low[v]);
}
else if(zh[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]!=dfn[u]){
return;
}
tot++;
while(stk[top]!=u){
zh[stk[top]]=0;
qfl[tot].push_back(stk[top]);
top--;
}
qfl[tot].push_back(stk[top]);
zh[stk[top]]=0;
top--;
}
void tarj(){
for(int i=1;i<=n;i++){
if(!fl[i])dfs(i,0);
}
}
|
复杂度
由于只进行一次DFS，甚至不需要存反边。所以总的复杂度是 $O(E)$。