什么？都3202年了，你还不会强连通分量？（二）
上节
这次我们来讲讲 Kosaraju 算法
Kosaraju 算法最早在 1978 年由 S. Rao Kosaraju 在一篇未发表的论文上提出，但 Micha Sharir 最早发表了它。
对于一个无向图的连通分量，从连通分量的任意一个顶点开始，进行一次 DFS，一定能遍历这个连通分量的所有顶点。所以，整个图的连通分量数应该等价于遍历整个图进行了几次（最外层的）DFS。一次 DFS中遍历的所有顶点属于同一个连通分量。
Why？为什么？
显然上图中有两个强连通分量，即强连通分量A和强连通分量 B，分别由顶点 A0-A1-A2 和顶点 B3-B4-B5 构成。每个连通分量中有若干个可以相互访问的顶点（这里都是 3 个），强连通分量与强连通分量之间不会形成环，否则应该将这些连通分量看成一个整体，即看成同一个强连通分量。
我们现在试想能否按照无向图中求连通分量的思路求解有向图的强连通分量。我们假设，DFS 从强连通分量B的任意一个顶点开始，那么恰好遍历整个图需要 2 次 DFS，和连通分量的数量相等，而且每次 DFS 遍历的顶点恰好属于同一个连通分量。
如果你不理解上面这段话的话，可以换种方式理解：
依靠两次 DFS 实现：
第一次 DFS，选取任意顶点作为起点，遍历所有未访问过的顶点，并在回溯之前给顶点编号，也就是后序遍历。
第二次 DFS，对于反向后的图，以标号最大的顶点作为起点开始 DFS。这样遍历到的顶点集合就是一个强连通分量。对于所有未访问过的结点，选取标号最大的，重复上述过程。
两次 DFS 结束后，强连通分量就找出来了，Kosaraju 算法的时间复杂度为 O(n+m)。
补充一个知识点：什么是反图？
举个栗子：原图 \text{G} 的逆图 \text{GT} ，其定义为 \text{GT=(V,ET)} ，\text{ET={(u,v):(v,u)∈E}}。也就是说 \text{GT} 是由 \text{G} 中的边反向所组成的，通常也称之为图 \text{G} 的转置。在这里值得一提的是，逆图 \text{GT} 和原图 \text{G} 有着完全相同的连通分支，也就说，如果顶点 \text{s} 和 \text{t} 在 \text{G} 中是互达的，当且仅当 \text{s} 和 \text{t} 在 \text{GT} 中也是互达的。
看看珂爱的代码
\text{Code}
// 注：g是原图，g2是反图
void dfs1(int u)
{
vis[u]=1;
for (int v:g[u]) if (!vis[v]) dfs1(v);
s.push_back(u);
}
void dfs2(int u)
{
color[u]=sccCnt;
for (int v:g2[u]) if (!color[v]) dfs2(v);
}
void kosaraju() {
sccCnt = 0;
for (int i = 1; i <= n; ++i)
if (!vis[i]) dfs1(i);
for (int i = n; i >= 1; --i)
if (!color[s[i]]) {
++sccCnt;
dfs2(s[i]);
}
}
cpp
那啥啥？我有考虑到有Py党的同志，所以……我又去学了一下Py的写法……
def dfs1(u):
vis[u] = True
for v in g[u]:
if vis[v] == False:
dfs1(v)
s.append(u)
def dfs2(u):
color[u] = sccCnt
for v in g2[u]:
if color[v] == False:
dfs2(v)
def kosaraju(u):
sccCnt = 0
for i in range(1, n + 1):
if vis[i] == False:
dfs1(i)
for i in range(n, 0, -1):
if color[s[i]] == False:
sccCnt = sccCnt + 1
dfs2(s[i])
py
下次继续，链接会在讨论区~
参考资料：