# 课前零食：从共享房间到圆方树

> 圆方树不是“再给图换一套很玄的名字”。它处理的是一个很朴素的尴尬：两个结实的小团体可以共用同一个人；把人硬塞进互不重叠的组里，反而把信息弄丢了。今天我们先把这件尴尬画出来，再给“团体”发一张方形身份证。

## 本节目标

学完后，你能：

- 从删点实验中认出割点与点双连通分量（vertex-biconnected component）分别在描述什么；
- 解释为什么点双分量可以共享割点，不能像强连通分量那样直接缩成互不重叠的点；
- 手工把一张无向图变成圆方树（block-cut tree），并在树上读出必经的割点；
- 跟踪边栈在何时弹出一个点双块，知道条件 low[child] ≥ dfn[parent] 的人话含义；
- 用“原点是圆、块是方”的统一视角，为后面的路径统计和树上 DP 搭好框架。

## 前置知识与课前自测

前置：无向图、DFS 树、桥和割点的直觉。不会写 Tarjan 也没关系；本节会先用暴力删除验证。

1. 删除一个点 C 后图分成两块，C 自己该归到哪一块？
2. 三角形 A-B-C-A 中，删掉 B 后 A 与 C 还连通吗？
3. 两个“删掉任一点仍有路绕开”的大块，能共享两个原图顶点吗？

<details><summary>先别急着看：自测答案</summary>

1. 它往往同时是多块的门口，硬选一边会丢掉另一边的归属。2. 仍连通，直接走 A-C。3. 不能。若共享两个点，这两块可经两个公共点拼成更大的点双块；真正的重叠只能是一处割点。

</details>

## 互动规则：把图当作一栋有门的房子

请在纸上画下面的无向图；边都是双向走廊：

~~~text
三角形一：A-B-C-A
三角形二：C-D-E-C
走廊链：  C-F-G
~~~

纸上分四栏：**对象**（现在有哪些房间、走廊）、**状态**（删掉谁、DFS 到哪）、**动作**（本轮能沿哪条走廊）、**账本**（哪些点属于哪些结实团体）。每次遇到“停顿”，先写答案，再展开或运行程序。

贯穿问题不是“背出圆方树定义”，而是：从 A 去 E、从 A 去 G 时，哪些门卫绝对绕不过？如果后来要问很多次路径，能否只在一棵树上回答？

## 从零搭框架：先让“一个人属于两组”真的发生

### 第 0 步：暴力拆房，先不许用 low

依次把 C、F 从图上擦掉，并从 A 出发标记还可到达的点。记录：

| 被删除的点 | A 一侧还看见谁 | 另一侧有哪些点 | 这说明什么 |
|---|---|---|---|
| C |  |  |  |
| F |  |  |  |

> 停顿 0：删 C 后，A、B、D、E、F、G 分成哪几堆？C 若是“某个团的成员”，它要属于几团？

<details><summary>展开：第一处不能硬分组的地方</summary>

删 C 后有 {A,B}、{D,E}、{F,G} 三堆，所以 C 是割点。它同时是三角形 ABC、三角形 CDE 与走廊 CF 的端点。若把 C 只分给其中一个团，另两个团与 C 的连接信息就被擦掉了；这正是“普通缩点”不够用的原因。

</details>

### 第 1 步：先找真正结实的局部

把三角形 ABC 圈起来。删除其中任一顶点，剩下两点仍有边相连；所以它内部没有一个单点能把其余成员拆开。CDE 也一样。单条走廊 CF 虽然没有绕路，但在以边为单位的点双分解里，它也形成一个含 C、F 的块：它提醒我们这条连接只经由两端。

> 停顿 1：为什么“删 C 后 A 到 E 断了”不等于“ABC 这个三角形不结实”？请分别写出这两个问题删除后的剩余对象。

<details><summary>展开：块内结实，与块间门口是两层问题</summary>

ABC 问的是只看 A、B、C 这个小块时，删一个点后剩余点是否仍连通；删 C 后 A-B 仍有边。A 到 E 的问题却跨了两个块，所有跨越都要经过 C。点双块负责保存局部可绕性，割点负责说明块与块之间的唯一门口。

</details>

### 第 2 步：发明方点，而不是复制原点

试过“给每个点双块涂一种颜色”后，C 会被迫涂三种颜色。不要复制 C；复制的是**块这个关系**。做法如下：

1. 原图每个顶点保留一枚圆点；
2. 每个点双块新建一枚方点；
3. 方点与属于该块的全部圆点连边。

请为 ABC、CDE、CF、FG 分别画方点 Q1、Q2、Q3、Q4，再连到对应圆点。

![一个割点可同时属于多个点双块](../插图/02-强连通与双连通/00-圆方树-01-共享点双块.svg)

> 停顿 2：在你新画出的图中，圆点 C 的度数是多少？从圆点 A 到圆点 G 的唯一路径经过哪些方点和圆点？

<details><summary>展开：把重叠改写成树边</summary>

C 连 Q1、Q2、Q3，度数为 3。A 到 G 的路径是 A-Q1-C-Q3-F-Q4-G；其中 C、F 是原图中绕不过的割点。原图的“块重叠”被方点吸收后，连接关系变成树状，不再需要在一张有环图里猜所有绕路。

</details>

### 第 3 步：为什么结果真会是一棵树

先只看连通原图。每加入一个新点双块，它若和已经出现的块共享两个原点，就会与旧块合并成更大的点双块，矛盾；因此它只会通过一个割点接到已有部分。每个新方点像给树挂上一颗新叶子，圆方图不会出现环。

这一步很重要：圆方树不是“把原图画得好看”，而是用一棵树保存原图的**块—割点骨架**。原图的一条边落在某个方点内部；跨块路径则只能在圆方树中穿过相应圆点。

## 问题动机：暴力删点会重复做太多次

刚才逐个擦点很直观，但若有 n 个点、m 条边，每删一个点都重做一次 DFS，会接近 O(n(n+m))。我们需要在一次 DFS 中记住：某个孩子子树有没有一条边能绕回父亲之前的祖先。

![DFS 的一段走廊何时封成一个块](../插图/02-强连通与双连通/00-圆方树-02-边栈与封口.svg)

## 步步式引导：把尚未封口的走廊放进边栈

### 1. 边栈里放的不是“访问顺序”，而是暂未归属的边

从 A DFS。每走一条树边，或看见一条通往祖先的返祖边，就把**边编号**压进栈。为什么不是压顶点？因为 C 需要出现在多个块里；一条边却恰好属于一个点双块，最后可以放心交出去。

令 dfn[u] 是 u 首次被看到的时间，low[u] 是从 u 的 DFS 子树出发，经零条或多条树边、至多一条返祖边，能碰到的最早祖先时间。

当树边 u-v 满足：

$$
low[v]\ge dfn[u],
$$

v 子树再也不能绕到 u 的上方。栈顶直到边 u-v 为止的走廊恰好封成一个点双块；把它们弹出，新建一个方点。

### 2. 先翻译不等式，再看伪代码

- low[v] < dfn[u]：子树能从侧门绕到 u 的祖先，暂时不能封口；
- low[v] = dfn[u]：能绕回 u 本人，却到不了上方；在 u 这里封口；
- low[v] > dfn[u]：连 u 也绕不回，这条树边还是桥；它仍对应一个只有这条边的块。

> 停顿 3：在图中从 C 走到 F，再走到 G。G 返回 F 时为什么必然封出 FG？F 返回 C 时为什么又会封出 CF？

<details><summary>展开：没有旁路的走廊会逐段结账</summary>

G 没有返祖边，low[G]=dfn[G]，大于 dfn[F]，所以弹出 FG。随后 F 的 low 仍是 dfn[F]，大于 dfn[C]，再弹出 CF。桥不是“圆方树做不了的边”；它恰好是一个极小的方块，只连接它的两个端点。

</details>

~~~text
DFS(u, parent_edge):
    dfn[u] = low[u] = next_time()
    for edge e=(u,v):
        if e is parent_edge: continue
        if v is unvisited:
            push e onto edge_stack
            DFS(v, e)
            low[u] = min(low[u], low[v])
            if low[v] >= dfn[u]:
                pop edges through e as one block
                create one square node for their endpoints
        else if dfn[v] < dfn[u]:
            push e onto edge_stack
            low[u] = min(low[u], dfn[v])
~~~

适用条件：这里是静态无向图。重边必须按边编号跳过父边，不能把“连到父亲”全跳过；否则另一条平行边提供的绕路会消失。

## 核心知识：圆点与方点各自承诺什么

| 节点 | 表示 | 它连向谁 | 读路径时意味着什么 |
|---|---|---|---|
| 圆点 | 原图一个顶点 | 包含它的方点 | 可能是割点，也可能只是块内成员 |
| 方点 | 一个点双连通块 | 该块的原顶点 | 在块内部可以绕开单个成员 |

原图连通时，圆方树是一棵树；原图不连通时得到森林。两原点间在原图跨越的点双块顺序，就是圆方树上两圆点之间的路径。若题目询问“从 u 到 v 必经多少个割点”，常可在这条树路径上统计度数大于 1 的圆点（但要按题目是否计端点调整）。

正确性的账本有两层：边栈弹出的边在边界出现前不能和更早边组成同一块；边界出现时它们又通过 DFS 路径和返祖边连成最大块。每条边压、弹各一次，Tarjan 与建树总计 O(n+m)，树有至多 n 加上块数个节点。

## 实现指南

- 给每个原点预留圆方树编号 1..n；新方点从 n+1 起编号，弹出一块才分配。
- 弹栈时收集边的两个端点；对每个不同端点 v，加圆方树边 square-v。
- 用时间戳数组去重“本块出现的端点”，不要为每块清空 O(n) 的集合。
- 根是否是割点的判定需要 DFS 儿子数；但边栈的点双块弹出仍按 low[child] ≥ dfn[parent] 执行。
- 孤立点没有边栈块；题目若要把它放进圆方树，可只保留孤立圆点。不要无依据地造一个方点。

## 纸上模拟：让边栈真的开一次账

按邻接顺序 A→B→C→D→E→F→G DFS。先在纸上补全表；返祖边 E-C 和 C-A 是最关键的两笔。

| 返回的孩子边 | low[孩子] | 与父亲 dfn 比较 | 弹出的边 | 新方点 |
|---|---:|---|---|---|
| D-E |  |  |  |  |
| C-D |  |  |  |  |
| F-G |  |  |  |  |
| C-F |  |  |  |  |
| A-B |  |  |  |  |

<details><summary>展开：一份可核对的边栈流水线</summary>

E 经返祖边回到 C，所以 low[E]=dfn[C]；D 返回 C 时 low[D]=dfn[C]，弹出 C-D、D-E、E-C，得到 CDE。G 返回 F 时弹 FG；F 返回 C 时弹 CF。C 还能经 C-A 回到 dfn[A]，所以 B 返回 A 时才弹 A-B、B-C、C-A，得到 ABC。每一批弹出的边只交给一个方点。

</details>

接着在你画出的圆方树上圈出 A 到 E、D 到 G 两条路径。问自己：若原图某条块内边替换成另一条块内边，圆方树路径会变吗？不会；圆方树刻意忘掉了块内部细节，只保留“从哪个门进、从哪个门出”的结构。

## 互动小实验室

运行 [从共享房间到圆方树.py](../../互动程序/02-强连通与双连通/00-从共享房间到圆方树.py)。它会先请你预测删 C 的结果，再打印边栈的压入、弹出和生成的方点。可输入：

- show：查看原图、点双块和圆方树邻接表；
- delete C：用朴素 DFS 验证删点后的连通块；
- path A G：查看圆方树上两圆点的路径；
- trace：重新逐步打印 Tarjan 的账本。

先预测 Q1 到 Q4 中哪一个方点会连接 C，再运行；程序只是验算员，不会替你补纸上的箭头。

## 扩展与联系

- 圆方树也叫块割树；“圆/方”只是方便画图的称呼，不代表图论中另一个神秘对象。
- 边双连通分量彼此不共享原点，缩成桥树即可；点双块共享割点，才需要额外方点。
- 块内若要继续处理最短路、计数或 DP，圆方树不足以代替原图；它只保存块与块之间的骨架。
- 动态加删边会改变点双块边界，静态 Tarjan 与静态圆方树不能直接维护。

## 总结与自检

1. 为什么方点代表点双块、圆点仍代表原图顶点？
2. 两个点双块为什么至多共享一个原点？
3. low[child] ≥ dfn[parent] 的一句人话是什么？
4. 为什么边栈比顶点栈适合提取点双块？

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

方点把可重叠的“成员关系”外置；共享两个点会使两块合并；孩子子树无法绕到父亲上方；割点可以反复属于不同块，边却恰好只交给一个块。

</details>

## 一周预热安排

- 第 1 天：在两三角形共一点的图上暴力删点，写下连通块。
- 第 2 天：手建 Q1、Q2、Q3、Q4，沿圆方树回答必经门口。
- 第 3 天：只模拟一次边栈的压入和第一次弹块。
- 第 4 天：运行互动程序，比较暴力删点和 low 的结账时刻。
- 第 5 天：进入[割点、点双连通分量与圆方树入口正式课](03-割点点双连通与圆方树入口.md)。