Tarjan 强连通分量NOIP

💡 核心思想

Tarjan 算法用于在有向图中求强连通分量（SCC）。核心是 DFS 过程中维护 dfn（时间戳）和 low（能回溯到的最早时间戳），当 low[u] == dfn[u] 时，栈中 u 及其之后的节点构成一个 SCC。

🎯 直觉理解

Tarjan 算法求强连通分量（SCC）：有向图中"两两互相可达"的最大点集。一个 SCC 可以当成一个"铁哥们圈子"——内部随便互相到达。

核心是 DFS 时间戳 + 低链接值 low：$dfn[u]$ 是 u 被访问的次序，$low[u]$ 是 u 的子树能回溯到的最早祖先。当 $dfn[u]==low[u]$ 时，栈顶到 u 的这一段就是一个 SCC。

应用：缩点（把每个 SCC 压缩成一个点，图就变成 DAG，可以拓扑排序 + DP）、判强连通。理解"low 值"是 Tarjan 的难点——它记录的是"这个点最远能顺着回边爬回哪"。

📝 算法流程

1. DFS 遍历，记录 dfn 和 low
2. 遇到已访问且在栈中的节点则更新 low
3. 当 low[u] == dfn[u] 时弹出栈中元素直到 u，构成一个 SCC
4. SCC 可以缩点后在 DAG 上做 DP

$$low[u] = \min \left( dfn[u], \min_{v \in \text{子树}} dfn[v], \min_{(u,v) \text{是返祖边}} dfn[v] \right)$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
vector g[10005];
int dfn[10005], low[10005], stk[10005], top = 0, ts = 0;
bool inStk[10005];
int sccCnt = 0, sccId[10005];
void tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    stk[top++] = u; inStk[u] = true;
    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        sccCnt++;
        int v;
        do { v = stk[--top]; inStk[v] = false; sccId[v] = sccCnt; } while (v != u);
    }
}
int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) { int u,v; cin>>u>>v; g[u].push_back(v); }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
    cout << sccCnt << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目