【图论】Kosaraju算法详解

桃扇骨 2023-07-24 09:29 20阅读 0赞

讲 Kosaraju 算法之前要先知道什么是强连通分量（SCC）

**强连通分量**

*  对于一个有向图顶点的子集 S ，如果在 S 内取两个顶点 u 和 v ，都能找到一条从 u 到 v 的路径，那么就称 S 是强连通的。
 *  如果在强连通的顶点集合 S 中加入其他任意顶点集合后，它都不再是强连通的，那么就称 S 是原图的一个强连通分量（SCC:strongly connected component）。
 *  任意有向图都可以分解成若不相干的强连通分量，这就是强连通分量分解。
 *  把分解后的强连通分量缩成一个顶点，就得到了一个DAG（有向无环图）。

如图，图中有 3 个强连通分量（SCC），将三个强连通分量缩成一个顶点，就得到了有向无环图（DAG）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]

**Kosaraju 算法**

*  Kosaraju 算法可以计算出一个有向图的强连通分量（SCC）。
 *  Kosaraju 算法基于两个原理：
    
    （1）一个有向图 G，把 G 的所有的边反向，建立反图 rG，反图 rG 不会改变原图 G 的强连通性。也就是说，图 G 的 SCC 数量与 rG 的 SCC 数量相同。
    
    （2）对原图 G 和反图 rG 各做一次 DFS，可以确定 SCC 数量。
 *  对原图 G 做一次 DFS 是为了确定点的先后顺序，用到了拓扑排序。在DFS过程中，把递归到最底层的那个点标记为最小，然后回退过程中，其他点的标记逐个递增。即优先级小的点先存，优先级大的点后存。
 *  对反图 rG 做一次 DFS ，顺序从标记最大的点开始到最小的点。为什么顺序要相反？因为在反图中，方向相对于原图都相反了，优先级大的点由出度多，变成了入度多，那么 DFS 过程中就会被反边堵住，也就是说，此时能搜索到的点都是同个强连通分量的点。按照这个顺序依次搜索下去。

**步骤：**

（1）先记录原图 G 和反图 rG  
（2）对原图所有的点 DFS 一遍，标记点的先后顺序  
（3）根据点的逆序 DFS 一遍，能搜到的点就是在同一个强连通分量。

**例题：** [HDU - 1269 迷宫城堡][HDU - 1269]

**题意：** 一个有向图，有 n 个点（n <= 10000）和 m 条边（m <= 100000）。判断整个图是否强连通，如果是，输出 “Yes”，否则，输出“No”。

**思路：** Kosaraju 算法模板题，直接求整个图是否为强连通分量。

**Code：**

#include <iostream>
    #include <cstring>
    #include <vector>
    using namespace std;
    const int N = 100010;
    vector<int> G[N],rG[N];
    vector<int> S;  // 存第一次dfs1()的结果，即标记点的先后顺序，优先级小的点先进
    int vis[N];    // vis[i]标记第一次dfs1()点i是否访问过
    int sccno[N];  // sccno[i]标记点i属于第几个强连通分量，同时记录dfs2()过程中点i是否访问过
    int cnt;    //cnt表示强连通分量的个数
    void dfs1(int u){ 
        if(vis[u])  return;
        vis[u] = 1;
        for(int i=0; i<G[u].size(); i++)
            dfs1(G[u][i]);
        S.push_back(u); //记录点的先后顺序，按照拓扑排序，优先级大的放在S的后面
    }
    
    void dfs2(int u){ 
        if(sccno[u])    return;
        sccno[u] = cnt;
        for(int i=0; i<rG[u].size(); i++)
            dfs2(rG[u][i]);
    }
    void Kosaraju(int n) { 
        cnt = 0;
        S.clear();
        memset(vis,0,sizeof(vis));
        memset(sccno,0,sizeof(sccno));
        for(int i=1; i<=n; i++) //搜索所有点
            dfs1(i);
        for(int i=n-1; i>=0; i--){ 
            if(!sccno[S[i]]){ 
                cnt++;
                dfs2(S[i]);
            }
        }
    }
    int main() { 
        int n,m,u,v;
        //坑点，这里 n 或者 m 都不能为 0 
        while(cin >> n >> m && (n || m)) { 
            for(int i=0; i<n; i++) { 
                G[i].clear();
                rG[i].clear();
            }
            for(int i=0; i<m; i++) { 
                cin >> u >> v;
                G[u].push_back(v);  // 原图
                rG[v].push_back(u); // 反图
            }
            Kosaraju(n);
            cnt==1? cout<<"Yes"<<endl:cout<<"No"<<endl;
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]: /images/20230528/326f1952ce83489cab72e8d0aeb82823.png
[HDU - 1269]: http://acm.hdu.edu.cn/showproblem.php?pid=1269