[图论] 求强联通分量

定义

在一个有向图中，如果存在两个顶点 $x$ 和 $y$ 有一条 $x$ 到 $y$ 的路径，还有一条从 $y$ 到 $x$ 的路径，则称这两个顶点强连通。如果有向图 $G$ 的每两个顶点都强连通，则称 $G$ 是一个强连通图。有向图的极大强连通子图，称为强连通分量

做法

强连通分量可以通过 $tarjan$ 算法求解

与求割点和桥类似，我们都需要定义两个数组 $dfn$ 和 $low$，将 $dfs$ 过程中的每一个节点压入栈中

但此时 $low$ 表示能到达的仍在栈内的最远祖先

在枚举完 $x$ 每一个能到达的节点 $v$ 后，如果 $dfn[x] == low[x]$，将栈弹出直至栈顶 $k == x$，中间的所有点组成了一个强连通分量

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;
const int MAXN = 100000 + 10;
const int MAXM = 200000 + 10;

int Head[MAXN], to[MAXM], Next[MAXM], tot = 1;
int dfn[MAXN], low[MAXN], time_stamp;

stack <int> Sta;
vector <int> scc[MAXN];
int sccNo[MAXN], scc_cnt;

int n, m;

inline int read(){
    int x = 0;
    char ch = getchar();

    while(ch < '0' || ch > '9'){
        ch = getchar();
    }

    while('0' <= ch && ch <= '9'){
        x = x*10 + ch - '0';
        ch = getchar();
    }

    return x;
}

inline void add(int a, int b){
    to[tot] = b;
    Next[tot] = Head[a];
    Head[a] = tot++;    
}

inline void tarjan(int x){
    dfn[x] = low[x] = ++time_stamp;

    Sta.push(x);

    for(register int i=Head[x]; i; i=Next[i]){
        int v = to[i];

        if(!dfn[v]){
            tarjan(v);
            low[x] = min(low[x], low[v]);
        }else if(!sccNo[v]){
            low[x] = min(low[x], dfn[v]);
        }
    }

    if(dfn[x] == low[x]){
        scc_cnt++;

        while(true){
            int tmp = Sta.top();
            Sta.pop();

            sccNo[tmp] = scc_cnt;
            scc[scc_cnt].push_back(tmp);

            if(tmp == x){
                break;
            }
        }
    }
}

inline void find_scc(){
    for(register int i=1; i<=n; i++){
        if(!dfn[i])
            tarjan(i);
    }
}