SCC 与 kosaraju 算法

Strongly Connected Components

强连通分量，一个图 $G$ 的子图 $G'$ 中，任意两个店都可以通过子图中的路径，直接或间接地联通，那么我们就称 $G'$ 是 $G$ 中的一个强连通分量。

强连通分量的两个性质：

连通性 - 指所有的点都可以通过边直接或间接地联通；
最大化 - 该子图必须是最大子图，也就是说一个强连通分量不能是其他强连通分量的子图。

kosaraju 算法

有趣的事实

kosaraju 本人于 $1978$ 年提出该算法，但未发表论文，Sharir 在 $1981$ 年发明了同样一种算法，发表了论文，经证实，Sharir 和 Kosaraju 都是独立发明的该算法，但是 Aho, Hopcroft 和 Ullman 相信这个算法是由 Kosaraju 在 $1978$ 在一个未发表的论文上提出的。

所以，Kosaraju 的算法，也称为 Kosaraju-Sharir 算法。

思路与实现过程

在以下这幅图中，有三个强连通分量，分别是 $1,2,3$ 和 $4,5,6,7$ 和 $8$ 。

我们将三个强连通分量各自看成一个点，会发现可以构成一张图，这三个强连通分量组成的图是一张 有向无环图 (DAG)。

在 Strongly Connected Components 这篇论文中，有这样一句话：

Every directed graph is a dag of its strongly connected conpoments.（译：每个有向图都是关于他强连通分量的 DAG）

那么在下面这个图片上，我们来讲解一下 kosaraju 算法的过程和思路。

如果我们从 $8$ 开始 dfs，那么我们会搜索到 $3$ 和 $7$ 这两个点，很显然， $8$ 、 $3$ 和 $7$ 并不在同一个强连通分量之内，所以这样显然是不太符合预期的。

从何下手？

如果我们从 $7$ 这个点开始 dfs，那么会搜索到 $4$ 、 $5$ 和 $6$ 这样我们搜索到的点都属于同一个强连通分量，因为 $4-5-6-7$ 这个强连通分量是整张图里的一个 sink（汇，指有入度，无出度的点，在这里指有入度，无出度的强连通分量）。如果我们可以选择一个 sink 开始 dfs，那么就可以找到这个 sink 的整个强连通分量，然后删掉这个 sink，再找下一个 sink，进行 dfs。

这样我们就可以一次找出所有的强连通分量了。

如何寻找 sink？

定理：一个有向图 $G$ 的强连通分量，与其反图 $G'$ 的强连通分量相同。

我们可以从任意一个点开始 dfs，进行 dfs，并按照回溯顺序将点压进栈中。

还是以下属这个图为例：

我们从 $1$ 号点开始深搜，搜索顺序为： $1\rightarrow 3\rightarrow 2\rightarrow 3\rightarrow 7\rightarrow 4\rightarrow 5\rightarrow 6\rightarrow 5\rightarrow 4\rightarrow 7\rightarrow 3\rightarrow 1$ 。

回溯顺序就是 dfs 最后一次访问的顺序。

依次为： $2\rightarrow 6\rightarrow 5 \rightarrow 4\rightarrow 7\rightarrow 3\rightarrow 1$ 。

在这次 dfs 中， $8$ 号点没有被访问，但是我们不用担心。

在这次 dfs 的 $7$ 个点（不含 $8$ 号点）的子图中，最后回溯的点所在的强连通分量，在反图中是 sink，于是我们再反图中进行 dfs 即可找到这个强连通分量。

然后删除这个强连通分量的所有点，找剩下的点中找最后回溯的点在反图中再次进行 dfs 即可。

然后将这个子图 $G'$ 在 $G$ 中，删除，对剩下的点继续刚才的操作即可。

知道所有点都被分配过了强连通分量，就可以结束搜索了。

以上就是 kosaraju 算法的实现过程。

对于每个点，都进行过两次 dfs，时间复杂度 $O(n)$ ，常数比一次 dfs 的 tarjan 稍大一些。

核心代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7;
vector<int> g[N],rg[N];
bool done[N];
int scc[N],tot=0;
vector<int> dfn;

void dfs(int id) {
	done[id]=1;
	for(auto c:g[id])
		if(!done[c]) dfs(c);
	dfn.push_back(id);
}

void calscc(int id) {
	cout<<id<<' ';
	scc[id]=tot;
	for(auto c:rg[id])
		if(!scc[c]&&done[c]) calscc(c);
}

void kosaraju() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;++i) {
		int st,ed;
		cin>>st>>ed;
		g[st].push_back(ed);
		rg[ed].push_back(st);
	}
	for(int i=1;i<=n;++i) 
		if(!done[i]) {
			dfn.clear();
			dfs(i);
			for(int i=dfn.size()-1;i>=0;--i) {
				int idx=dfn[i];
				if(scc[idx]) continue;
				tot++;
				cout<<"SCC #"<<tot<<": ";
				calscc(idx);
				cout<<'\n';
			}
		}
}

int main() {
    kosaraju();
    return 0;
}

模板题：B3609 强连通分量。

通过 SCC 缩点后，可以整张图会变成一个 DAG，可以参考 DAG 上问题这篇文章求解最长路和拓扑序。

另一种求解 SCC 的算法为：tarjan 算法。