强连通分量 Tarjan 算法 - NOI提高级教程

📖 算法原理：DFN 序、LOW 追溯与栈判定

在有向图 $G = (V, E)$ 中，若两个顶点 $u$ 和 $v$ 之间存在双向路径，则称它们是强连通的。有向图的极大强连通子图称为强连通分量（SCC，Strongly Connected Component）。

📐 Tarjan 算法核心追溯概念

DFN 序 (dfn[u])：顶点 $u$ 被 DFS 深度搜索遍历到的绝对时间戳（步数）。
LOW 值 (low[u])：以 $u$ 为根的 DFS 搜索子树中的节点，通过至少一条非树枝逆向边，能追溯到的最小时间戳 DFN。
Tarjan 辅助栈：DFS 搜索过程中，把当前搜索路径上的点依次压入栈中。
回溯更新公式：

若探索到未访问邻居 $v$，递归进行 DFS，回溯时更新：$low[u] = \min(low[u], low[v])$
若邻居 $v$ 已经在栈中（说明是一条反向强连通边），则直接更新：$low[u] = \min(low[u], dfn[v])$

SCC 判定条件：当 DFS 回溯完成，若发现某个节点满足 $dfn[u] == low[u]$，说明以 $u$ 为根的子树上的点构成了一个独立的强连通分量！此时将栈中的元素依次弹出，直到 $u$ 出栈。

📥 Tarjan 深度追溯辅助栈 (Tarjan Active Stack)

栈为空

🏆 已识别的强连通分量列表 (Discovered SCCs)

暂无强连通分量

选择图 Preset：

演示速度：

选择预设图并点击"开始 Tarjan 算法"观摹 dfn 与 low 在深度搜索栈中的动态更新与物理缩点。

🕸️ Tarjan 二阶追溯深度遍历网 (Tarjan DFN / LOW Visual Map)

int dfn[MAXN], low[MAXN], timer = 0;
bool instack[MAXN];
stack<int> st;

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    st.push(u); instack[u] = true;
    
    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]); // 树枝边回溯更新
        } else if (instack[v]) {
            low[u] = min(low[u], dfn[v]); // 反向回退边更新
        }
    }
    
    if (dfn[u] == low[u]) { // 发现 SCC 根节点
        while (true) {
            int v = st.top(); st.pop();
            instack[v] = false;
            scc[v] = scc_cnt; // 缩点分配强连通分量ID
            if (u == v) break;
        }
        scc_cnt++;
    }
}

📋 算法执行步骤历史