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

## 本节目标

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

## 前置知识与课前自测

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

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

<details><summary>自测答案</summary>

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

</details>

## 问题动机

对每个点做一次可达性 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`，含义是否完全相同？

<details><summary>展开区别</summary>

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

</details>

## 核心知识与正确性

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

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

## 实现指南

```text
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](https://vjudge.net/problem/CodeForces-427C)
- 原题：[Codeforces Round 244 (Div. 2)](https://codeforces.com/problemset/problem/427/C)
- 难度：1700；考点：SCC 内独立选择、乘法计数

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

<details><summary>Hint 1</summary>一个检查站能保护的范围恰是它所在 SCC。</details>
<details><summary>Hint 2</summary>每个 SCC 至少选一个点；费用最优时只能选该 SCC 的最小费用点。</details>
<details><summary>Hint 3</summary>不同 SCC 的选择互不影响，所以方案数相乘。</details>

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/02-强连通与双连通/CodeForces-427C.cpp)

### 复盘与变式

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

## 精选例题 2：Network of Schools

### 来源信息与题意

- VJudge：[POJ-1236 Network of Schools](https://vjudge.net/problem/POJ-1236)
- 原来源：IOI 1996
- 大致难度：提高；考点：缩点 DAG 的源点/汇点、最少补边

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

<details><summary>Hint 1</summary>先缩 SCC；同一 SCC 中从哪所学校开始没有区别。</details>
<details><summary>Hint 2</summary>DAG 中入度为 0 的分量无法由别的分量获得软件。</details>
<details><summary>Hint 3</summary>若不止一个分量，第二问答案是 `max(源点数, 汇点数)`。</details>

### Observations、Editorial 与证明

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

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

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

```text
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](../../参考实现/02-强连通与双连通/POJ-1236.cpp)

### 复盘与变式

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

## 精选例题 3：Popular Cows

### 来源信息与题意

- VJudge：[POJ-2186 Popular Cows](https://vjudge.net/problem/POJ-2186)
- 原来源：USACO 2003 Fall
- 大致难度：提高；考点：唯一汇 SCC

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

<details><summary>Hint 1</summary>若答案中的两头牛互相不可达，能否同时被所有牛到达？</details>
<details><summary>Hint 2</summary>缩点后，候选只能位于出度为 0 的 SCC。</details>
<details><summary>Hint 3</summary>DAG 有且仅有一个汇点时，每个点都能到达它。</details>

### Observations、Editorial 与证明

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

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

```text
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](../../参考实现/02-强连通与双连通/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` 要刻意做一次“源/汇方向”反例。