Tarjan算法求SCC

求有向图的强连通分量。

Tarjan 的核心在于 DFS，在 DFS 过程中，我们会遇到如下 4 种边：

• 树枝边：DFS 过程中经过的边，即 DFS 搜索树上的边。
• 前向边：从祖先节点指向后代节点的非树枝边，我们称为前向边。
• 后向边：从后代节点指向祖先节点的非树枝边，我们称为后向边。
• 横叉边：两端无祖先关系的非树枝边，我们称为横叉边（只会向左）。

定义：

• dfn[u]：结点u的时间戳。
• low[u]：追溯值：结点u能回溯到的时间戳最小点。
• timestamp：时间戳。
• stk[N], top, in_stk[N]：栈，存未被处理的点。
• id[u]：u对应scc编号。
• siz[v]：编号为v的scc的结点数。

缩点，将原图转换为DAG图：

vector<int> g[N];
int dfn[N], low[N], timestamp;
int stk[N], top; bool in_stk[N];
int id[N], scc_cnt, siz[N];

void tarjan(int u){
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = 1;
    for(auto &v : g[u]){
        if(!dfn[v]){ 
            tarjan(v); // 如果没有搜到过，开搜
            low[u] = min(low[u], low[v]); // 更新追溯值
        }
        else if(in_stk[v]) low[u] = min(low[u], dfn[v]);
    }               // 如果搜到过并且在栈中(即尚未处理)，用它的dfn更新追溯值
    
    if(dfn[u] == low[u]){   // 代表这个点是强连通分量的头头
        ++scc_cnt;     // 计数scc
        int y;
        do{
            y = stk[top--];   // 出栈
            in_stk[y] = 0;    // 记录出栈
            id[y] = scc_cnt;  // 更新该scc内结点的id (即归属到该scc中)
            siz[scc_cnt]++;   // 记录该scc大小
        }while(y != u);       // 走到头头了，结束
    }
}