有向图的强连通分量（Tarjian）

强连通分量

有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

下图中，子图{1,2,3,4}为一个强连通分量，因为顶点1,2,3,4两两可达。{5},{6}也分别是两个强连通分量。

Tarjian算法

对于一个强连通分量 ，从任何一个点出发都能遍历整个图。假设 第一个发现的点为 ，那么在访问完 的所有子节点直接输出就是这个 ，可是我们不知道这个点是不是

问题转化为判断一个点是否为

假设当前的点为 。

如果从 的子节点可以到达 的祖先节点，那么 肯定不是他所在的 第一个被发现的点。如果从 的子节点最多只能到达 ，那么

vector<int> G[maxn];
int pre[maxn], low[maxn], sccno[maxn], dfs_clock, scc_cnt;
stack<int> s;

void dfs(int u){
    pre[u] = low[u] = ++dfs_clock;          // 标记每个点访问时间
    s.push(u);
    for (int i = 0; i < G[u].size(); i++){  // 遍历 u 所有子节点
        int v = G[u][i];
        if(!pre[v]){
            dfs(v);
            low[u] = min(low[u], low[v]);    // 用子节点的 low 值更新 u 的 low 值。
        }else if(!sccno[v])                  // 如果 v 不属于 SCC
            low[u] = min(low[u], pre[v]);    // 反向边更新 u 的 low 值
    }
    if(low[u] == pre[u]){                   // 如果 u 及其后代最早能达到的祖先只能到 u
        scc_cnt++;                          // u 就是 SCC 访问第一个点
        while(1){
            int x = s.top();
            s.pop();
            sccno[x] = scc_cnt;
            if(x == u)
                break;
        }
    }
}


void find_scc(int n){
    dfs_clock = scc_cnt = 0;
    memset(sccno, 0, sizeof sccno);
    memset(pre, 0, sizeof pre);
    for(int i = 0; i < n; i++){
        if(!pre[i])
            dfs(i);
    }
}