【笔记】Tarjan SCC

/*
 * @Author: thyzzs
 * @Date: 2019-08-02 16:55:56
 * @LastEditTime: 2019-11-14 09:44:57
 */
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define MAX_N 1000005
using namespace std;
//定理：一个SCC从其中任何一个点出发，都至少有一条路径能绕回自己

int cnt;                          // 强连通分量个数
int low[MAX_N], num[MAX_N], dfn;  // num[]代表dfs对每个点的访问顺序，low[]代表能返回到的最远祖先的num值
                                  // 相同low值代表一个SCC，初始low值等于num
                                  // dfn代表进入递归的顺序，用于给num赋值（时间戳）
int scc[MAX_N], stack[MAX_N], top;  // stack[]模拟栈，top是栈顶
vector<int> G[MAX_N];

inline void dfs(int u) {
    stack[top++] = u;  // u进栈
    low[u] = num[u] = ++dfn;
    for (register int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!num[v]) {  // 未访问过的点，继续dfs
            dfs(v);
            low[u] = min(low[v], low[u]);
        } else if (!scc[v])  // 处理回退边
            low[u] = min(low[u], num[v]);
    }
    if (low[u] == num[u]) {  // 栈底的点是SCC的祖先，它的low = num
        cnt++;
        while (1) {
            int v = stack[--top];  // v弹出栈
            scc[v] = cnt;
            if (u == v) break;  // 栈底的点是SCC的祖先
        }
    }
}

inline void Tarjan(int n) {
    cnt = top = dfn = 0;
    memset(scc, 0, sizeof(scc));
    memset(num, 0, sizeof(num));
    memset(low, 0, sizeof(low));
    for (register int i = 1; i <= n; i++)
        if (!num[i]) dfs(i);
}

int main() {
    int n, m, u, v;
    scanf("%d%d", &n, &m);
    for (register int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
    }
    Tarjan(n);
    return 0;
}