SCC 与 kosaraju 算法

· · 算法·理论

Strongly Connected Components

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

强连通分量的两个性质：

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

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 稍大一些。

核心代码

vector<int> g[105];
vector<int> rg[105];
bool done[105];
int scc[105];
vector<int> dfn;
int tot=0;

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';
            }
        }
}

有兴趣的同学可以尝试一下此题：https://www.luogu.com.cn/problem/B3609

B3609 的 AC 代码：https://www.codepaste.cn/#/cd/503e6fbc-f9c8-45fc-9952-814ff121937c
AC 记录：https://www.luogu.com.cn/record/102550455