强连通分量与缩点

强连通分量（Strongly Connected Components, SCC） 是有向图分析的核心工具，其本质是将图中的环结构等价折叠，将一般有向图降维为有向无环图（DAG）。

---

一、 核心概念与缩点意义

• 强连通分量（SCC）：有向图中，一些点可以彼此相互到达，这些点就构成一个强连通分量。

• 缩点转化为 DAG：一个强连通分量缩成一个点后，原图会变成有向无环图（DAG）。

• 求解手段：由于 DAG 中无环，最常用的求解手段是拓扑排序或 DAG 动态规划。

• 正确性前提：缩点建模必须保证缩点之后求解答案不受影响（例如环上点权全选或可达性等价）。

• 算法选择：竞赛中掌握 Tarjan 算法即可应对绝大多数 SCC 场景。

---

二、 Tarjan 算法必备状态与模型

Tarjan 算法基于深度优先搜索（DFS）树和辅助栈展开。

1. 边的分类

• 树边：DFS 生成树上的边，指向未访问过的节点。

• 回边：指向当前搜索栈中祖先节点或横叉到栈内合法节点的边。

• 弃边：指向已经完成 SCC 划分并已出栈节点的边。

2. 状态定义与容器

• dfn[u]：节点 $u$ 获得的 DFS 访问序号（时间戳）。

• low[u]：$u$ 及其子树上的点，最多走一条回边能到达的树的最上方点的 $dfn$ 序号。

• belong[u]：节点 $u$ 分配的强连通分量序号；若为 0 表示尚未分配。

• 栈 sta：用来收集遍历到的节点；节点遍历到时先进栈，一旦该节点分配了强连通分量，就从栈中弹出。

---

三、 算法流程（“扎口袋”模型）

Tarjan 算法直观上可理解为“扎口袋算法”：

1. 初次访问：初次来到 $u$ 时，$dfn[u]=low[u]=$ 分配的 dfn 序号，然后节点 $u$ 进栈。

2. 遍历出边：遍历 $u$ 的每个儿子 $v$，分类讨论边类型：

• 若为弃边（即 $dfn[v]>0$ 且不在栈内），什么也不做。

• 若为树边（$dfn[v]==0$），先递归计算 $low[v]$，回溯时更新 $low[u]=min(low[u],low[v])$。

• 若为回边（$dfn[v]>0$ 且在栈内），直接更新 $low[u]=min(low[u],dfn[v])$。

3. 扎口判定：遍历结束后，判断 $dfn[u]$ 是否等于 $low[u]$：

• 若不相等，代表节点 $u$ 不能扎起口袋，继续向上回溯更新更高层祖先。

• 若相等，代表节点 $u$ 能扎起口袋，栈持续弹出节点直到 $u$ 出现时停止，这批节点构成一个独立的强连通分量。

4. 全图覆盖与复杂度：考察图中每个节点，一旦发现 $dfn[i]==0$，就从该节点开始执行一遍 Tarjan 算法。最终求出全部强连通分量，时间复杂度为 $O(n+m)$，其中 $n$ 为节点数，$m$ 为边数。

---

四、 核心辨析：回边更新到底是 dfn[v] 还是 low[v]？

在回边转移逻辑中存在经典疑问：当节点已被访问且仍在栈中（belong[v] == 0）时，更新式应写 low[u] = min(low[u], dfn[v]) 还是 low[u] = min(low[u], low[v])。

• 等价性（在有向图 SCC 中）：两者最终划分出的 SCC 结果完全一致。只要 $v$ 在栈中，说明 $v$ 已经属于当前连通块，无论传入 $dfn[v]$ 还是 $low[v]$，都能确保 $low[u]<dfn[u]$，不会导致子树提前弹栈，也不会漏掉节点。
• 数学严格性：根据定义，$low[u]$ 表示至多走一条回边能回溯的最上方点。low[v] 可能已经通过其他回边更新过，若代入 low[v] 则逻辑上走了多条非树边，违背了数学定义。

---

模板

#include <algorithm>
#include <vector>

constexpr int N = 2e5 + 5;

// 原图与 DAG
std::vector<int> g[N], dag[N];
int dfn[N], low[N], timer;
int stk[N], top;
int belong[N], scc_cnt;
int in_deg[N];

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;

    for (int v : g[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = std::min(low[u], low[v]);
        } else if (!belong[v]) { // 在栈内即为回边
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++scc_cnt;
        while (true) {
            int x = stk[top--];
            belong[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

// 缩点并去除重边
void build_dag(int n) {
    for (int u = 1; u <= n; ++u) {
        for (int v : g[u]) {
            if (belong[u] != belong[v]) {
                dag[belong[u]].push_back(belong[v]);
            }
        }
    }
    for (int i = 1; i <= scc_cnt; ++i) {
        std::sort(dag[i].begin(), dag[i].end());
        dag[i].erase(std::unique(dag[i].begin(), dag[i].end()), dag[i].end());
        for (int v : dag[i]) {
            ++in_deg[v];
        }
    }
}

---

强连通分量与缩点题单