# 课前零食：树多长出一条边

> 树的世界很规矩：两点之间只有一条简单路。基环树只多了一条边，就突然多出一个能绕圈的地方。诀窍不是假装它还是树，而是先把那一圈找出来。

## 本节目标

学完后，你能：

- 识别“连通 $n$ 点 $n$ 边”为什么恰有一个简单环；
- 用不断剥离叶子的过程把环从挂树中露出来；
- 将无向基环树与每点出度为 1 的函数图联系起来；
- 理解为什么环上决策常需单独处理首尾，而树上的信息可向环汇总。

## 前置知识与课前自测

前置：树、度数、队列、DFS/BFS。

1. 连通树有 $n$ 个点时有多少条边？
2. 在树上额外加一条边，为什么至少会产生一个环？
3. 一个度数为 1 的叶子可能在一个简单环上吗？

<details><summary>答案</summary>

1. $n-1$。2. 新边两端在树中原本已有唯一一条路径，新边和这条路径闭合成环。3. 不可能；环上的点至少接着环的前一条和后一条边，度数至少为 2。

</details>

## 互动规则：每次删点前先说出“它为什么不可能在环上”

准备图 `A-B,B-C,C-A,B-D,D-E,C-F,C-G`。每个点旁先写当前度数；每删一个点，划掉它、给未删邻点的度数减 1，并写一句证词：“它为什么不可能在唯一环上？”不要一开始把剩余点叫“环”，先让删除过程证明它。

函数图实验另用一张纸：每点恰一条出箭头，记录的是**入度**。这两种剥离动作看起来相像，但删的理由不同。

## 从零搭框架：先从树的唯一性出发

### 第 0 步：树为什么没有绕圈的余地

画一棵 5 点树，例如 `A-B,A-C,C-D,C-E`。从 A 到 D 找路径；再尝试找一条不重复边的第二条路径。请数边数，并尝试删掉任意一条边。

> 停顿 0：为什么连通且无环的 5 点图必须有 4 条边？若有第 5 条边，它的两个端点原本在树中已有怎样的关系？

<details><summary>展开：额外边只能闭合已有路径</summary>

树中两点之间有唯一简单路径。第 5 条边连接其两个端点时，和原路径合成一个环；连通 $n$ 点 $n$ 边图因此至少有环。它只比树多一条边，所以不会凭空长出两份独立绕圈空间，恰有一个简单环。

</details>

### 第 1 步：先把“肯定不在环上”的点找出来

回到预设图。请填初始度数，圈出所有度数为 1 的点；然后假装你要在一个环上绕路，问：能否经过度数 1 的 E 后离开它而不重复边？

| 点 | A | B | C | D | E | F | G |
|---|---:|---:|---:|---:|---:|---:|---:|
| 初始度数 |  |  |  |  |  |  |  |
| 被删后剩余度数 |  |  |  |  |  |  |  |

> 停顿 1：删 E 后 D 变成什么？为什么 D 这时才获得“绝不在环上”的证书？

<details><summary>展开：剥叶不是猜环，而是排除非环</summary>

初始叶子为 E、F、G。叶子只有一条未删边，若从它进入就没有另一条边离开，故不在环上。删 E 后 D 的剩余度数变 1，D 也可删；最后 A、B、C 均剩度数 2，形成唯一环。每次删点都只传播“它的邻居少了一条边”。

</details>

### 第 2 步：把队列状态说完整

请把无向剥叶的状态补全：

```text
degree[u] = ______
queue = ______
removed[u] = ______
弹出 u 后，对每个 ______ 的邻点 v：______
```

> 停顿 2：为什么不直接把所有当前度数小于等于 1 的点反复扫描？队列替你省掉了什么重复劳动？

<details><summary>展开：每条边只负责一次度数通知</summary>

`degree` 是未删邻边数；队列初始装度数 1 点；`removed` 防止重复处理；删 u 时仅对未删邻点减度数，若变 1 入队。扫描全图会反复寻找新叶子；队列只在某点刚满足条件时通知一次，总边访问线性。

</details>

### 第 3 步：函数图为什么改剥入度 0

画箭头 `A→B,B→C,C→A,D→C,E→D,F→E`。沿每点唯一出边前进，先从 F 开始写路线。请标出所有入度为 0 的点并按队列删除。

> 停顿 3：为什么出度 1 的 F 仍可以先删？为什么删 F 后该减少 E 的入度而不是出度？

<details><summary>展开：谁没人指向，谁不可能在有向环上</summary>

环上每个点至少被环的前驱指向，入度不可能为 0；每点出度固定为 1，所以它不能作为筛子。删 F 代表“没有任何路线会绕进 F 再成环”，其唯一出边原本贡献给 E 的入度，故要减 E 的入度。最后剩 A、B、C 的有向环。

</details>

### 第 4 步：环找出来后，问题才被允许分家

请把预设无向图分为“环 `A-B-C-A`”和挂在 B/C 上的树。若每个删掉的叶子有一个值要汇总到离环更近的点，应该在“入队、弹出、还是最后遍历环”哪个时刻累加？

<details><summary>展开：外向内的删除顺序就是汇总顺序</summary>

在弹出叶子时把它的贡献加给唯一未删邻点；这样 D 会先收到 E，再把完整贡献送给 B。环点最后拿到各自挂树摘要。之后环上的首尾相邻关系必须单独处理，不能当成普通树父子关系。

</details>

## 问题动机：把基环树当普通树会在哪儿摔倒

若从任一点 DFS，把访问过的邻点全当父亲或已处理点，环会让“父子关系唯一”的假设失效；做树形 DP 时，环的首尾也会互相依赖。可如果先把所有挂在环外的树枝削掉，最后留下的正是唯一环，问题就分成“环外树”和“环上小问题”两部分。

![树加一条边后出现唯一环](../插图/09-基环树/00-基环树-01-多一条边.svg)

## 步步式引导

### 1. 为什么是“唯一”环

一棵连通 $n$ 点树有 $n-1$ 边；额外加一条边会得到至少一个环。若存在两个不同简单环，删其中一个环上一条不被另一个环必需的边仍可能保持连通，边数便可继续降到低于树的下界，矛盾。更直观地说：从树加的那条边只有一次机会闭合原来的唯一树路径。

### 2. 叶子为什么可以安全剥掉

叶子不在环上，删掉它不会删掉任何环。删叶子后，它唯一邻点的度数减 1；这个邻点可能变成新的叶子，继续入队。直到队列空，所有剩余点度数都至少为 2；在连通单环图中，它们恰好组成那条环。

![一层层剥叶后只剩环](../插图/09-基环树/00-基环树-02-剥叶.svg)

```text
queue = every vertex whose degree is 1
removed[all] = false
while queue not empty:
    u = queue.pop_front()
    removed[u] = true
    for v in neighbors[u]:
        if not removed[v]:
            degree[v] -= 1
            if degree[v] == 1:
                queue.push_back(v)
cycle_vertices = every vertex not removed
```

这和拓扑排序很像：不是按有向先修关系剥入度 0，而是按“绝不可能在环上”的无向叶子剥度数 1。

### 3. 函数图只是箭头版的同一故事

若每个点恰有一条出边，沿箭头一直走必会重复，因此每个弱连通块有一个有向环，其他点都是指向环的树。把入度为 0 的点不断删掉，剩下的就是环点；方向换了，但“剥掉不能在环上的部分”的思想没换。

```text
queue = all vertices with indegree 0
while queue not empty:
    u = queue.pop_front()
    v = to[u]
    indegree[v] -= 1
    if indegree[v] == 0:
        queue.push_back(v)
remaining vertices are directed-cycle vertices
```

## 纸上模拟：让队列自己露出核心

对预设无向图，填写每一轮队列和度数变化：

| 弹出点 | 它的未删邻点 | 邻点新度数 | 新入队点 | 当前剩余点 |
|---|---|---:|---|---|
| E |  |  |  |  |
| F |  |  |  |  |
| G |  |  |  |  |
| D |  |  |  |  |

再对函数图写入度序列，按 `F,E,D` 删除。最后请分别写一句：“无向图剩余点为何组成环？”“函数图剩余点为何组成有向环？”

<details><summary>展开：相似队列，两个不变量</summary>

无向图中 E 让 D 变叶，F、G 使 C 的度数降到 2，D 再使 B 降到 2，剩 A/B/C；函数图中 F 使 E 入度 0，E 使 D 入度 0，最后 A/B/C 都仍有环内前驱。一个维护未删度数，一个维护未删入度；它们都在排除“不可能属于核心”的点。

</details>

## 核心知识：先切环，后做树，再回到环

剥叶顺序天然从外向内。若每个被删点有一个要向父亲汇总的值，可以在弹出时累加到唯一未删邻点；最后每个环点拿到了自己挂树的完整信息。环上若有“相邻不能同时选”之类约束，常把一个点强制选或不选，做两次链 DP，避免把首尾当作互不相干。

整个剥叶过程每条边导致至多一次度数下降，复杂度 $O(n)$。适用前提很重要：无向部分须是连通 $n$ 点 $n$ 边；一般图可能剩多个环或复杂核心，不能把“剩余点都是唯一环”照搬。

## 实现指南

- 无向图初始化队列的条件是 `degree == 1`，函数图是 `indegree == 0`；别把两种剪刀拿反。
- 标记已删除点，避免一条边在两端被删后继续重复减度数。
- 环点通常还需按环顺序走一圈；“未删除”只是集合，不自动给出环顺序。
- 如果图允许不连通，应对每个分量分别判断；`n` 点 `n` 边只保证全图环数总量，不保证每块各一个。

## 互动小实验室

运行 [树多长出一条边.py](../../互动程序/09-基环树/00-树多长出一条边.py)。选择 `u` 可观察无向图从叶子到环的剥离顺序；选择 `f` 可观察函数图的入度剥离。程序会在每一步打印哪一个点已不可能在环上。

先预测预设图里 $D$ 何时变成叶子；然后改看函数图，比较“度数 1”和“入度 0”这两个相似却不同的条件。

## 扩展与联系

基环树的“核心 + 挂树”分解会通向环上计数、删环边直径和函数迭代；更一般的图中，反复剥叶留下的称为 2-core。树形 DP 能处理挂树，环上的首尾依赖则提醒你不要把一圈强行掰成一条没有说明的链。

## 总结与自检

1. 为什么叶子不可能是唯一环的一部分？
2. 剩余点集合为何还不等于“已经得到环顺序”？
3. 函数图剥的是入度而不是出度，原因是什么？

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

环上点至少有两条环边；集合没有记录相邻次序；每点出度固定为 1，只有没有人指向的点不可能在任何有向环上。

</details>

## 一周预热安排

- 第 1 天：从一棵树加一条边，圈出产生的环。
- 第 2 天：手做一次度数 1 剥叶队列。
- 第 3 天：把箭头版函数图的入度写在每个点旁。
- 第 4 天：运行互动程序，解释每个被删点为何不可能在环上。
- 第 5 天：进入[剥叶找环与环上统计正式课](01-剥叶找环与环上统计.md)。