有向图的强连通分量

基本概念

在有向图G中，如果两个顶点u, v间存在一条从u到v的有向路径，并且同时存在一条从v到u的有向路径，则称这两个顶点强连通。

如果有向图G的任意两个顶点都强连通，则称G是一个强连通图。

有向图的极大强连通子图，称为强连强分量。

求强连通分量常用的方法有Kosaraju和Tarjan算法，这里介绍最简单而通用的Kosaraju算法。

Kosaraju算法

算法步骤：

1. 对原图g进行dfs，记录每个节点的离开时间
2. 选择最晚离开时间的顶点，对反向图G进行dfs，删除能够遍历到的顶点，这些顶点构成一个强连通分量
3. 如果还有顶点没被删除，继续上一步，否则结束

#include <bits/stdc++.h>
using namespace std;
vector<int> g[10005], G[10005], seq, scc[10005];
int vis[10005], id[10005], nscc;
void dfs1(int x) {
    vis[x] = 1;
    for (auto i : g[x])
        if (!vis[i]) dfs1(i);
    seq.push_back(x);
}
void dfs2(int x) {
    id[x] = nscc;
    scc[nscc].push_back(x);
    for (auto i : G[x])
        if (!id[i]) dfs2(i);
}
void find_scc(int n) {
    for (int i = 1; i <= n; i++)
        if (!vis[i]) dfs1(i);
    for (int i = n-1; i >= 0; i--) {
        if (!id[seq[i]]) {
            nscc += 1;
            dfs2(seq[i]);
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        G[b].push_back(a);
    }
    find_scc(n);
    cout << "scc num: " << nscc << endl;
    for (int i = 1; i <= nscc; i++) {
        for (auto j : scc[i])
            cout << j << " ";
        cout << endl;
    }
    return 0;
}