# 课前零食：从互相绕路到缩点

> 这杯零食给“会 DFS、但一看到 `low` 就想把电脑合上”的同学。先把图压成更好理解的形状，再进正式课学严谨的一次 DFS 写法。

## 本节目标

学完后，你能：

- 用“能去也能回来”辨认强连通分量（Strongly Connected Component, SCC）；
- 明白为什么一群互相可达的点可以缩成一个点，且缩完一定没有有向环；
- 用删边、删点的小实验认识桥（bridge）和割点（articulation point）；
- 知道正式课里的 `dfn/low/栈` 各在避免什么重复工作。

## 前置知识与课前自测

前置：有向边、无向边、DFS/BFS、连通块。请先回答：

1. 有向边 $A\to B$ 存在时，$B$ 一定能回到 $A$ 吗？
2. 若 $A$ 能来回到 $B$，$B$ 能来回到 $C$，$A$ 与 $C$ 的关系如何？
3. 一条无向边若躺在一个环上，删掉它会把环断成两个连通块吗？

<details><summary>答案与最小理由</summary>

1. 不一定；箭头不是自动折返券。2. $A$ 与 $C$ 也互相可达，因此“互相可达”可以把点分组。3. 不会，环的另一侧仍能绕过去；这正是“不是桥”的证据。

</details>

## 互动规则：先把“能到”写成箭头账本

这节有两张不同的图，千万别混在一张纸上：一张是**有向图**，问“能去又能回来”；另一张是**无向图**，问“删掉谁后断开”。每张纸都画四栏：`我从谁出发`、`这一步沿了哪条边`、`我还能回到谁`、`这条边/点被删后谁失去联系`。

遇到 `low`、缩点、桥这些词时，先把它们盖住。你要先亲自回答：**哪些点真的扮演同一种“可达角色”？哪条路只是绕远，哪条路是唯一通道？**

## 从零搭框架：把重复问路压成一张地图

### 第 0 步：先区分单向能到与互相能到

画有向边：`A→B, B→C, C→A, C→D, D→E, E→D, E→F`。从每个点出发，先只做最普通的 DFS/BFS，并把下表填成“能/不能”：

| 出发点 | 能到 A | 能到 C | 能到 D | 能到 F |
|---|---|---|---|---|
| A |  |  |  |  |
| D |  |  |  |  |
| F |  |  |  |  |

> 停顿 0：`A` 能到 `D`，`D` 能到 `A` 吗？哪些点既能从 A 到达、又能回到 A？先圈成一团。

<details><summary>展开：先得到最原始的分组</summary>

`A,B,C` 可以两两来回；`D,E` 可以两两来回；`F` 只能留在自己的单点团。单向可达不是对称关系，不能直接分组；“互相可达”才可以。

</details>

### 第 1 步：让暴力法自己暴露重复工作

若对每个点都做一次 DFS，就能得到完整的可达表，复杂度约为 $O(V(V+E))$。请在刚才的图上标色：从 A 的 DFS 会反复看 `A,B,C` 的环；从 B 再出发时，又会把同一个环里的边检查一遍。

> 停顿 1：把 `A,B,C` 压成一个大圆，`D,E` 压成一个大圆，`F` 保留单点。压完后边还剩怎样的方向？有没有环？

<details><summary>展开：缩点不是丢信息，而是删掉无用区分</summary>

得到三个点 `ABC→DE→F`。团内任何点对“能否到团外”的角色相同，许多问题不必再区分它们。若缩点后仍有环，环上团可以沿环互相到达，本应合为同一团，矛盾；所以缩点图一定是 DAG。

</details>

### 第 2 步：先证明“互相可达”能安全分组

请为下面三句各写一条路线拼接理由，而不是只写“显然”：

1. 任意点能回到自己吗？
2. 若 $u$ 能来回到 $v$，那么 $v$ 能来回到 $u$ 吗？
3. 若 $u$ 能来回到 $v$，$v$ 能来回到 $w$，怎样拼出 $u$ 到 $w$ 和 $w$ 到 $u$ 的路线？

<details><summary>展开：等价关系给了我们缩点许可</summary>

三条分别是自反、对称、传递。尤其传递性允许把一圈关系扩成一个最大团，而不是得到许多互相重叠的小团。SCC 是“互相可达”的等价类，不是 DFS 恰好走到的一坨点。

</details>

### 第 3 步：如何不做 $n$ 次 DFS 就把团找出来

先接受一个适合手算的框架：第一次 DFS 不急着分组，只记录“一个点的所有后继都处理完”的**完成时刻**；第二次把所有箭头倒过来，按完成时刻从晚到早出发收集点。

请在下表中模拟从 A 的第一次 DFS。每当一个点没有未访问后继时，把它写进 `finish`：

| 返回到的点 | 此时哪些后继已处理完 | `finish` 尾部 |
|---|---|---|
| F |  |  |
| E |  |  |
| D |  |  |
| C |  |  |

> 停顿 3：为什么第二轮要把箭头反过来？若仍在原图按倒序出发，从 A 会不会一路跑到 D、E、F？

<details><summary>展开：反图把“团的入口”封起来</summary>

第一次完成序列为 `F,E,D,C,B,A`。在反图中先从 A 出发只能收集 `A,B,C`，不会沿原来 `C→D` 的方向越界；之后收 `D,E`，最后收 F。把两次 DFS 看成一种易懂的脚手架；正式课会把它压缩成 Tarjan 的一次 DFS、栈和 `low` 不变量。

</details>

### 第 4 步：换成无向图，问题完全换了

擦掉箭头，画边：`A-B, B-C, C-A, C-D, D-E, E-F, F-D`。先不用任何公式，做两个物理实验：

1. 用橡皮擦掉 `A-B`；A 和 B 还能通过谁相遇？
2. 擦掉 `C-D`；左右两坨还能相遇吗？
3. 擦掉点 C（连同边）；哪几坨会分开？

> 停顿 4：给“删边断开”和“删点断开”各起一个临时名字，再看下方正式名字。

<details><summary>展开：桥和割点也是“有没有绕路”</summary>

`A-B` 在三角形中可绕 `A-C-B`，不是桥；`C-D` 无替代路线，是桥；删 C 会把左侧和右侧分开，C 是割点。这里不再问“能否回来”，而是问一棵 DFS 子树有没有通往祖先的旁路；它与 SCC 的 `low` 名字相同但含义不同。

</details>

## 问题动机：重复问路太浪费

如果要知道任意两点是否互相可达，最暴力的做法是从每个点都 DFS 一遍。$n$ 个点会得到 $O(n(n+m))$ 的工作量；更糟的是，我们反复发现同一个环里的点本来就是“同一团”。

例如 $A\to B\to C\to A$，再有 $C\to D$，$D\leftrightarrow E$，$E\to F$。在团内从谁出发都能绕回来；真正有价值的是团与团之间的单向关系。

![把互相可达的点缩成一个点](../插图/02-强连通与双连通/00-连通-01-缩点.svg)

## 步步式引导

### 1. “互相可达”为什么正好可以分组

把 $u$ 与 $v$ 放同组，当且仅当 $u$ 能到 $v$ 且 $v$ 能到 $u$。它有三种好性质：自己能到自己、关系可以倒过来、两段来回路可以接起来。因此它是等价关系，所有点被自然切成若干个 SCC。

若缩点图还有一个环，例如团 $P\to Q\to R\to P$，那么三个团里的任何点都能沿这些箭头互相到达，本应是同一团，矛盾。所以缩点后的图是 DAG。这个结论让很多“乱图”变成可以按方向依次处理的图。

### 2. 从两次走路自然得到 SCC

一种适合入门理解的办法是 Kosaraju：

1. 在原图 DFS，某点的所有能继续走的后代处理完后，记下它的完成顺序；
2. 把所有箭头反向；
3. 按完成顺序倒着出发，在反图中一次 DFS 能收集到的一团就是一个 SCC。

为什么不会串到别团？把一团看成缩点 DAG 的一个点。第一次 DFS 中，沿箭头能到达的团会更早完成；倒序挑出的团不会在反图中走进尚未收集的“错误团”。正式课的 Tarjan 把这两次旅行压缩进一趟 DFS：`low` 负责告诉我们能回到多早，栈负责暂存尚未封口的一团。

```text
finish = []
for every vertex u not visited:
    dfs_original(u) and append u when it finishes

for u in reverse(finish):
    if u not assigned:
        component = dfs_on_reversed_graph(u)
        output component
```

### 3. 无向图的“脆弱处”是另一种问题

现在把箭头擦掉。若删一条边后图被切开，它是桥；若删一个点（以及相连边）后图被切开，它是割点。它们都在问：某棵 DFS 子树能否借一条边绕回祖先？

![环边可以绕开，桥边不能](../插图/02-强连通与双连通/00-连通-02-桥与绕路.svg)

这里有一个容易混的对照：SCC 的 `low` 关注“仍在当前栈里的可回到位置”；桥/割点的 `low` 关注“子树能否绕到祖先”。名字相同，工作许可证不同，别把两张表硬嫁接。

## 纸上模拟：两张表，两个完全不同的问题

先对有向图完成 Kosaraju 的第二轮。把第一轮的 `finish=[F,E,D,C,B,A]` 写在纸上，倒过来依次尝试 `A,B,C,D,E,F`。每次从尚未分配的点出发，在**反图**中记录本轮收进的点：

| 尝试起点 | 是否已分配 | 反图 DFS 收到的点 | 新分量 |
|---|---|---|---|
| A |  |  |  |
| B |  |  |  |
| C |  |  |  |
| D |  |  |  |
| F |  |  |  |

<details><summary>展开：不要把“倒序”误读成“倒着走路线”</summary>

从 A 在反图收 `{A,B,C}`；B、C 已分配，跳过；从 D 收 `{D,E}`；最后从 F 收 `{F}`。倒序的是“选择新起点的完成顺序”，每一轮 DFS 仍沿反图箭头正向走。

</details>

再对无向图做一个低链前的人工验证。删除 `C-D` 后，以 A 为起点能访问到哪些点？删除 `A-B` 呢？请把结果写进：

| 删除对象 | A 所在连通块 | 另一侧还有谁 | 结论 |
|---|---|---|---|
| 边 `C-D` |  |  |  |
| 边 `A-B` |  |  |  |
| 点 `C` |  |  |  |

<details><summary>展开：low 公式要对应一条可见的旁路</summary>

删 `C-D` 时 A 侧是 `{A,B,C}`，D 侧是 `{D,E,F}`，它是桥；删 `A-B` 后所有点仍连通，因为有 `A-C-B`；删 C 后 A、B 与 D、E、F 分开，C 是割点。正式算法不是真的逐个删除，它只在 DFS 中记录“子树能绕到多早的祖先”，一次性推导出同样结论。

</details>

## 核心知识：删掉什么，谁就暴露出来

在无向 DFS 树中，若孩子 `v` 的整棵子树不能沿返祖边回到 `u` 之前的祖先，即 `low[v] > dfn[u]`，树边 $(u,v)$ 是桥。若非根 `u` 存在孩子使 `low[v] >= dfn[u]`，删除 `u` 后那棵子树无法接到上方，`u` 是割点。根要特殊处理：它有至少两个 DFS 孩子时才是割点。

这些条件不是魔法公式：把 `low[v]` 读成人话——“从 $v$ 子树出发，最早还能绕回 DFS 树的哪位祖先”。

小图上暴力删边/删点当然可以用来验证答案，但每次重做连通性会是 $O((n+m)^2)$ 量级。`dfn/low` 让一趟 DFS 汇总所有绕路信息，达到 $O(n+m)$。

## 实现指南

- 有向 SCC 和无向桥不能混用邻接表语义；先在纸上写清楚每条边是否有方向。
- 无向图要按**边编号**排除“父边”，不能按父节点排除；否则平行边会被误判成桥。
- SCC 缩点后若要建新图，可去重边，但先保留原边才能正确找分量。
- 递归 DFS 面对很深的链可能爆栈；正式提交时按题目范围改迭代或调整实现策略。

## 互动小实验室

运行 [从互相绕路到缩点.py](../../互动程序/02-强连通与双连通/00-从互相绕路到缩点.py)。选择：

- `1`：观察原图完成顺序、反图 DFS 和缩点结果；
- `2`：观察删桥/割点的低链值，并比较“有环可绕”和“桥无处绕”。

先在纸上预测 $C\to D$ 所在的位置会不会把两个 SCC 合并，再让程序揭晓。程序不是神谕，它只是一个不嫌你反复按回车的黑板。

## 扩展与联系

缩点 DAG 是许多 DP、最少补边和可达性题的起点；桥缩成边双连通分量后得到桥树；割点和点双连通分量会在后续圆方树中重现。现在只需牢牢记住两句话：有向图先看“能否回来”，无向图先问“有没有绕路”。

## 总结与自检

1. 缩点图为什么不可能有环？
2. 为什么平行边能救下一条看似孤独的树边？
3. 桥条件的严格大于和割点条件的非严格大于，分别对应什么？

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

缩点环会让环上团互相可达；另一条平行边提供了绕回父亲的路；桥要求完全绕不到父亲，割点只要求绕不到父亲之上。

</details>

## 一周预热安排

- 第 1 天：画三点有向环与单向链，圈出互相可达组。
- 第 2 天：手做一次“原图完成、反图收集”。
- 第 3 天：在无向小图上暴力删一条边、删一个点。
- 第 4 天：运行互动程序，读出一组 `dfn/low` 的人话含义。
- 第 5 天：进入[强连通分量与缩点正式课](01-强连通分量与缩点.md)。