lessons/课程/02-强连通与双连通/01-强连通分量与缩点.md

强连通分量与缩点：把有向环压成 DAG

本节目标

学完后，你应能从“互相可达”识别强连通分量（Strongly Connected Component, SCC），推导 Tarjan 的栈不变量，并在缩点 DAG 上解决选点、可达终点和最少补边问题。

前置知识与课前自测

前置：有向图 DFS、栈、DAG 入度/出度。

1. “$u$ 能到 $v$”是否构成等价关系？“$u,v$ 互相可达”呢？
2. DFS 搜到一条指向已访问点的边时，为什么不能一律更新 low？
3. 缩点后为什么不可能仍有有向环？

自测答案

1. 单向可达不对称；互相可达满足自反、对称、传递，构成等价关系。 2. 已经弹出 Tarjan 栈的点属于已封闭 SCC，当前未封闭分量不能通过它回到当前祖先。 3. 若若干 SCC 缩点后成环，环上各 SCC 两两可达，本应属于同一个 SCC，矛盾。

问题动机

对每个点做一次可达性 DFS 需要 $O(V(V+E))$。但许多题并不关心一个强连通区域内部怎样绕行：区域内任一点能承担相同的可达角色。若先把互相可达的点压成一个点，任意有向图就变成 DAG，入度、出度和拓扑结构才真正显露。

步步式引导：Tarjan 为什么只需一次 DFS

令 dfn[u] 为 $u$ 首次访问时间，low[u] 为从 $u$ 的 DFS 子树出发、只经过仍未封闭的点，能够回到的最小 dfn。

• 沿树边 $u\to v$ 完成递归后，用 low[v] 更新 low[u]；
• 遇到指向栈内点 $v$ 的非树边，用 dfn[v] 更新；
• 指向已出栈点的边忽略。

为什么 low[u]==dfn[u] 时可以弹栈？此时 $u$ 的子树无法回到 $u$ 之前仍未封闭的祖先；从栈顶弹到 $u$ 的所有点都能沿 DFS 树回溯关系回到 $u$，且从 $u$ 能沿树边到它们，正好形成一个极大的互相可达集合。

停顿：无向图求桥时也叫 low，含义是否完全相同？

展开区别

不完全相同。有向 SCC 的栈状态决定一条边是否能参与当前分量；无向桥算法按边编号排除父边，并关注子树能否借返祖边到达祖先。不要把两份更新规则机械混用。

核心知识与正确性

Tarjan 始终维护：栈中恰是已经访问但尚未归入 SCC 的点。每次发现根 low[u]==dfn[u]，弹出的集合内部互相可达；集合不能再加入更早或栈外点，否则 low[u] 会更小或那个 SCC 尚未封闭，产生矛盾。每点入栈、出栈各一次，每边扫描一次，时间 $O(V+E)$，空间 $O(V+E)$。

缩点时对原边 $u\to v$，若 scc[u] != scc[v]，就在分量间加边。是否去重取决于后续计算：只判断入度是否为零时可不去重；若统计边数或做 DP，重复边可能改变语义。

实现指南

DFS(u):
    dfn[u] = low[u] = next_timestamp()
    push u into Tarjan stack; mark u in_stack
    for v in graph[u]:
        if v is unvisited:
            DFS(v); low[u] = min(low[u], low[v])
        else if v is still in_stack:
            low[u] = min(low[u], dfn[v])
    if low[u] == dfn[u]:
        pop through u; all popped vertices form one SCC

上面是语义模板，不是可直接编译片段。递归深度最坏为 $V$；当 $V$ 达到数十万时，应确认评测栈限制，必要时改迭代 Kosaraju/Tarjan，不能把递归崩溃误判成算法错误。

精选例题 1：Checkposts

来源信息与题意

• VJudge：CodeForces-427C Checkposts
• 原题：Codeforces Round 244 (Div. 2)
• 难度：1700；考点：SCC 内独立选择、乘法计数

有 $n\le10^5$ 个路口、$m\le3\times10^5$ 条有向边，在点 $i$ 建检查站费用不超过 $10^9$。一个站能保护与它互相可达的点。求覆盖全部点的最小总费用，并在检查站数量也最少的前提下，求最优方案数模 $10^9+7$。

Hint 1

一个检查站能保护的范围恰是它所在 SCC。

Hint 2

每个 SCC 至少选一个点；费用最优时只能选该 SCC 的最小费用点。

Hint 3

不同 SCC 的选择互不影响，所以方案数相乘。

Observations、Editorial 与证明

把图分成 SCC。每个 SCC 外的点都不可能与其中点互相可达，因此每个分量至少建一个站；在分量内选费用最小点即可保护全分量，并且为了检查站数最少恰选一个。总费用是各 SCC 最小费用之和，方案数是各 SCC 中最小费用点数量的乘积。

下界“每分量至少一个”与构造“每分量恰选一个最小点”相等，故费用与数量均最优。复杂度 $O(n+m)$；总费用使用 long long。

核心伪代码与参考实现附件

components = Tarjan_SCC(graph)
total_cost = 0; ways = 1
for component in components:
    best = minimum(cost[v] for v in component)
    total_cost += best
    ways *= count(v in component where cost[v] == best)  (mod MOD)

完整 GNU C++17 参考实现见附件：CodeForces-427C.cpp

复盘与变式

若每个 SCC 要选至少 $k$ 个站，应取分量内前 $k$ 小并处理同价组合数；这时“只记录最小值与次数”不再够用。

精选例题 2：Network of Schools

来源信息与题意

• VJudge：POJ-1236 Network of Schools
• 原来源：IOI 1996
• 大致难度：提高；考点：缩点 DAG 的源点/汇点、最少补边

$2\le N\le100$，有向边表示软件可从一所学校传给另一所。第一问：至少给多少所学校初始软件，才能传遍全网？第二问：至少新增多少条有向边，才能从任意学校出发传遍全网？

Hint 1

先缩 SCC；同一 SCC 中从哪所学校开始没有区别。

Hint 2

DAG 中入度为 0 的分量无法由别的分量获得软件。

Hint 3

若不止一个分量，第二问答案是 `max(源点数, 汇点数)`。

Observations、Editorial 与证明

缩点得到 DAG。第一问必须在每个源 SCC 至少投放一次；从所有源出发能到达 DAG 的全部点，所以答案是源数。

第二问若已经只有一个 SCC，答案为 0。否则每个源至少要新增入边，每个汇至少要新增出边，故下界为两者最大值。把汇点与源点按可达关系适当排列，循环连接“第 $i$ 个汇到下一个源”，不足的一侧重复使用端点，即可用 max(source,sink) 条边让所有分量进入同一个环状可达结构，达到下界。

核心伪代码与参考实现附件

component = Tarjan_SCC(graph)
if there is only one component: output 1, 0
build condensation indegree and outdegree
sources = count(indegree == 0)
sinks = count(outdegree == 0)
output sources, max(sources, sinks)

完整 GNU C++17 参考实现见附件：POJ-1236.cpp

复盘与变式

第二问只要求最少数量，不要求实际输出补边；若要输出边，不能随意把任意汇与任意源循环相连而不证明整体强连通，需要构造与可达覆盖配合。

精选例题 3：Popular Cows

来源信息与题意

• VJudge：POJ-2186 Popular Cows
• 原来源：USACO 2003 Fall
• 大致难度：提高；考点：唯一汇 SCC

有 $N\le10^4$ 头牛与 $M\le5\times10^4$ 条有向“认可”关系，可达性具有传递含义。求被其他所有牛认可的牛数。

Hint 1

若答案中的两头牛互相不可达，能否同时被所有牛到达？

Hint 2

缩点后，候选只能位于出度为 0 的 SCC。

Hint 3

DAG 有且仅有一个汇点时，每个点都能到达它。

Observations、Editorial 与证明

若缩点 DAG 有多个汇 SCC，它们互相不可达，不可能存在被所有点到达的牛。若只有一个汇 SCC，则从任一分量沿出边最终必须落到某个汇，而汇唯一，所以所有分量都能到达它；其中每头牛均满足要求。答案因此是唯一汇 SCC 的大小，否则为 0。

核心伪代码与参考实现附件

component = Tarjan_SCC(graph)
compute every condensation component's size and outdegree
sink_components = components with outdegree 0
if len(sink_components) != 1: output 0
else: output size of the unique sink component

完整 GNU C++17 参考实现见附件：POJ-2186.cpp

复盘与变式

“所有点能到我”对应唯一汇 SCC；“我能到所有点”对应唯一源 SCC。方向翻转是本类题最常见的失误。

扩展与联系

• 2-SAT 用 SCC 判断变量与其否定是否落在同一分量，但赋值还依赖缩点后的逆拓扑关系。
• SCC 内部可压成一个状态做 DAG DP；若边权、计数允许重复路径，必须先明确重复跨分量边是否去重。
• Kosaraju 用正反图两遍 DFS，证明更直观、内存略多；Tarjan 一遍 DFS，状态更紧密。

总结与自检

1. dfn、low、in_stack 各表示什么？
2. 为什么遇到栈内边更新 dfn[v]，遇到已出栈点不更新？
3. 缩点 DAG 的源数和汇数分别解决了哪类下界？
4. 唯一汇 SCC 为什么一定被全部分量到达？

课后训练建议

先手写 Tarjan 并用暴力可达矩阵核对随机小图的分组；再依次阅读三题。Checkposts 应独立实现，Network of Schools 重点复述补边下界，Popular Cows 要刻意做一次“源/汇方向”反例。