# 基环树：剥叶找环、挂树大小与函数图计数

## 本节目标

识别无向连通 $n$ 点 $n$ 边图与每点出度 1 的函数图结构；用拓扑剥叶找出环，向环根汇总挂树信息，并完成环上独立决策。

## 前置知识与课前自测

前置：树、拓扑排序、DFS/BFS、计数原理。

1. 连通无向图有 $n$ 点 $n$ 边时恰有几个简单环？
2. 每点出度 1 的弱连通分量为何恰有一个有向环？
3. 反复删除度数 1 的点后，基环树中剩下什么？

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

1. 恰一个；相对树多出的唯一一条边产生唯一环。
2. 沿出边无限走必重复；两个不同有向环不可能在同一弱连通分量由出度 1 的边连接。
3. 环上点；挂树被从叶到根全部删除。

</details>

## 问题动机与核心知识

基环树（unicyclic graph/pseudotree）的关键不是“像树一样 DFS”，而是先分离唯一破坏树结构的环。无向图用度数剥叶；函数图用入度剥叶。被剥点形成指向环的树，剩余点构成一个或多个环。

剥叶还能顺便做 DP：无向图初始化 `size[v]=1`，叶子弹出时把大小加给唯一尚未删除邻点，最终每个环点的 `size` 就是它连同挂树的点数。

## 实现指南

- 无向剥叶判断 `degree==1`；孤立点不属于本主题的连通 n 边输入。
- 函数图删除 u 时只需降低 `indegree[to[u]]`。
- 遍历剩余环要单独 `visited`，不能依赖原 DFS 父亲。
- 环上 DP 常需“强制第一个选/不选”做两次链 DP，避免首尾状态冲突。

## 精选例题 1：Mouse Hunt

### 来源与题意

- [CodeForces-1027D Mouse Hunt](https://vjudge.net/problem/CodeForces-1027D)，难度 1700
- 每个点有代价 $c_i$ 且指向一个点 $a_i$；求打断所有无限追逐环的最小总代价。

<details><summary>Hint 1</summary>每个函数图弱连通分量只有环会导致无限循环。</details>
<details><summary>Hint 2</summary>每个有向环至少处理一个点，且不同环决策独立。</details>

### Observations

- 入树上的点最终必进入环，本身不形成新的无限循环。
- 打断一个环任选一个点即可，显然选最小代价。
- 入度剥叶无需递归，适合 $2\times10^5$ 深链。

### Editorial 与正确性证明

统计入度并删除入度 0 点；剩余点恰为所有有向环。逐环行走取最小代价并求和。任何可行方案必须触及每个环，否则该环仍无限；每环选择最小点能达到下界，环之间点不重叠，故全局最优。复杂度 $O(n)$。

### 核心伪代码与附件

```text
queue all vertices with indegree 0
while queue: remove u; decrease indegree[to[u]]
for each unvisited remaining vertex:
    walk its directed cycle and add minimum cost on this cycle
```

[完整 C++17 附件](../../参考实现/09-基环树/CodeForces-1027D.cpp)

## 精选例题 2：Number of Simple Paths

### 来源与题意

- [CodeForces-1454E Number of Simple Paths](https://vjudge.net/problem/CodeForces-1454E)，难度 2000
- 多组连通无向图，每组 $n$ 点 $n$ 边；统计所有无序点对之间的简单路径总数。

<details><summary>Hint 1</summary>同一挂树根下的两点只有一条简单路径。</details>
<details><summary>Hint 2</summary>挂在不同环点的两点有两条路径，分别走环两侧。</details>
<details><summary>Hint 3</summary>剥叶累计每个环点组大小 $size_i$。</details>

### Observations

- 每对点至少一条路径；是否多出一条只取决于它们的环归属是否不同。
- 不必枚举环点对，可用总点对减同组点对。
- 剥叶的大小汇总避免为每个环点重新 DFS 挂树。

### Editorial

剥叶并把被删点大小加给尚存邻点，得到环组大小 $s_i$。同组点对贡献 1，异组点对贡献 2。可从所有点对的基础 1 加异组数，等价公式为

$$
n(n-1)-\sum_i\frac{s_i(s_i-1)}2.
$$

### 正确性证明

同组两点之间若绕环另一侧必须重复经过组根，不是简单路径，故仅一条；异组两点到各自环根的树路径唯一，环上两条方向均不重复，故恰两条。所有点恰属一个环组，公式完整且不重。复杂度 $O(n)$。

### 核心伪代码与附件

```text
size[v] = 1
peel degree-1 vertices; when removing u, add size[u] to its remaining neighbor
answer = n * (n - 1)
for cycle vertex v:
    answer -= size[v] * (size[v] - 1) / 2
```

[完整 C++17 附件](../../参考实现/09-基环树/CodeForces-1454E.cpp)

## 精选例题 3：Directed Roads

### 来源与题意

- [CodeForces-711D Directed Roads](https://vjudge.net/problem/CodeForces-711D)，难度 1900
- 每点给一条连接到 $a_i$ 的道路，可任选两个方向之一；统计最终不存在有向环的定向方案，模 $10^9+7$。

<details><summary>Hint 1</summary>无向结构的每个函数图分量是一个环加挂树。</details>
<details><summary>Hint 2</summary>挂树边任意定向都不会单独形成环。</details>
<details><summary>Hint 3</summary>长度 L 的环有 $2^L$ 种定向，只排除两种全顺/全逆的有向环。</details>

### Observations、Editorial 与证明

入度剥叶后得到所有环。非环边共 $t$ 条，每条方向任意贡献 $2^t$；每个长度 $L$ 环贡献 $2^L-2$。一个环的混合方向必在某点断开，不能成为有向环；两种一致方向恰形成环。不同分量和边选择独立，相乘即答案。复杂度 $O(n)$。

### 核心伪代码与附件

```text
peel indegree-0 vertices; removed_count = number peeled
answer = pow(2, removed_count)
for each remaining directed cycle of length L:
    answer *= pow(2, L) - 2
```

[完整 C++17 附件](../../参考实现/09-基环树/CodeForces-711D.cpp)

## 扩展与联系

基环树最大独立集、直径等问题通常先做挂树 DP，再在环上做断环 DP。若每个分量可能有多环，就不再是基环树，剥叶后剩余的是一般 2-core，环上链式 DP 会失效。

## 总结与自检

1. 无向度数剥叶与函数图入度剥叶分别留下什么？
2. 挂树大小怎样在剥叶过程中汇总？
3. 异环组点对为什么恰有两条简单路径？
4. 环定向为什么只排除两种？

## 课后训练建议

用随机小函数图与 Floyd/枚举环核对剩余点；无向题枚举所有简单路径对拍。之后自行推导“基环树最大权独立集”的两次链 DP。