Tarjan 强连通分量CSP-S

💡 核心思想

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

🎯 直觉理解

想象在一个单向道路网络中，有些区域内的路口可以互相到达（强连通分量）。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 <bits/stdc++.h>
using namespace std;
vector<int> 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;
}

⚠️ 常见坑点

📚 相关题目