这篇文章上次修改于 349 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记15——强联通分量

问题与目的

强联通的点是指，A点能到达B点，且B点能到达A点。

对于一个图，问有多少强联通分量？

Kosaraju 算法

获取目标图G1的反图G2（所有边反向）

该算法先获取一张图G1所有点后序遍历的逆序排列。

再对G2进行dfs，每次dfs遇到的未到达的点集合就是一个强联通分量。

理解算法

首先我们要了解后序遍历的逆序排序意味着什么：

如果是一棵无环的树，后序排序的逆序一定是从根节点开始的，也就是说如果我们遍历一个点就删除它，我们就能保证，我们遍历到的每个点的时候（前面的点被删除）都是没有边指向它的。

如果这是一个连通图，再去寻找规律：

对于后序遍历的逆排序，对于其中的任意一个点，在这个点右边的所有点都是这个点能达到的，在这个点左边的所有点都是这个点碰不到的。

如果这图不一定联通，有规律：（这个规律就很重要）

这个点的后面的所有点都是这个点能到达的，或者根本不连通的（没有任何的边关系），前面的点都是到达不了的。

分析

对G2进行dfs，所有的边都反向了，此时的A点到达B点实际上就是B点能到达A点。

对所有的点从前往后运算，我们能保证，这个点后面的所有点只有两种情况，根本没有连接关系和能到达的点。例如第一个点，我们能保证除去和它根本无关的点，它能到达其他的所有点。

所以G2中，从前点开始能遇到的点，就是这些点能遇到前点，形成了一个强联通，一旦形成便删除，所以对于后面遍历的每个点都有这样的连接关系。

这也就是Kosaraju算法的原理。

代码

// g 是原图，g2 是反图

void dfs1(int u) {
  vis[u] = true;
  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]);
    }
}

例题一：

给定一个有向图，每个点i有点权ai，请对于每个点i，找到i能到达的点中点权的最大值（包括i点）。

对于题目要求，我们可以利用强联通分量，对于强联通分量中的每个点，它们能到达点点权最大值是一样的，所以不妨把一个强联通分量的点集合看做一个点，这就形成了一个有向无环图，再进行记忆化搜索即可。

void solve(){
    int n, m;
    int sccCnt = 0;
    int maxV = 0;
    cin >> n >> m;
    vector<int> value(n + 1);

    vector<int> value2(n + 1);

    for(int i = 1; i <= n; i++){
        cin >> value[i];
    }
    vector<int> G1[n + 1];
    vector<int> G2[n + 1];
    vector<int> G3[n + 1];

    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        G1[a].push_back(b);
        G2[b].push_back(a);
    }

    vector<int> order;
    vector<bool> visited(n + 1);
    vector<bool> visited2(n + 1);

    vector<int> type(n + 1);

    function<void(int)> dfs1 = [&](int u)
    {
        visited[u] = true;
        for (int x : G1[u])
            if (not visited[x])
                dfs1(x);
        order.push_back(u);
    };

    function<void(int)> dfs2 = [&](int u)
    {   
        maxV = max(maxV, value[u]);
        type[u] = sccCnt;
        visited2[u] = true;
        for (int x : G2[u])
            if (not visited2[x])
                dfs2(x);
    };

    long long result = 0;
    for (int i = 1; i <= n; i++)
        if(not visited[i]) dfs1(i);
    
    
    for (int i = n - 1; i >= 0; i--)
    {
        if (not visited2[order[i]])
        {
            maxV = 0;
            ++sccCnt;
            dfs2(order[i]);
            value2[sccCnt] = maxV;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int x:G1[i]){
            if(type[i] != type[x]){
                G3[type[i]].push_back(type[x]);
            }
        }
    }

    // 缩点完成
    vector<bool> done(n + 1);
    
    function<int(int)> dfs3 = [&](int u)
    {   
        if(done[u]) 
            return value2[u];

        for(int x: G3[u]){
            if(not done[x]){
                value2[x] = dfs3(x);
                done[x] = true;
            }
            value2[u] = max(value2[u], value2[x]);
        }
        done[u] = true;
        return value2[u];
    };

    for(int i = 1; i <= sccCnt; i++){
        if(not done[i]) dfs3(i);
    }

    for(int i = 1; i <= n; i++){
        cout << value2[type[i]] << endl;
    }

}

应用

我们可以将一张图的每个强连通分量都缩成一个点。

然后这张图会变成一个 DAG，可以进行拓扑排序以及更多其他操作。

举个简单的例子，求一条路径，可以经过重复结点，要求经过的不同结点数量最多。

Mai Icy