# 基环树：剥叶找环、挂树大小与函数图计数 ## 本节目标 识别无向连通 $n$ 点 $n$ 边图与每点出度 1 的函数图结构；用拓扑剥叶找出环，向环根汇总挂树信息，并完成环上独立决策。 ## 前置知识与课前自测 前置：树、拓扑排序、DFS/BFS、计数原理。 1. 连通无向图有 $n$ 点 $n$ 边时恰有几个简单环？ 2. 每点出度 1 的弱连通分量为何恰有一个有向环？ 3. 反复删除度数 1 的点后，基环树中剩下什么？
答案 1. 恰一个；相对树多出的唯一一条边产生唯一环。 2. 沿出边无限走必重复；两个不同有向环不可能在同一弱连通分量由出度 1 的边连接。 3. 环上点；挂树被从叶到根全部删除。
## 问题动机与核心知识 基环树（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$；求打断所有无限追逐环的最小总代价。
Hint 1每个函数图弱连通分量只有环会导致无限循环。
Hint 2每个有向环至少处理一个点，且不同环决策独立。
### 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$ 边；统计所有无序点对之间的简单路径总数。
Hint 1同一挂树根下的两点只有一条简单路径。
Hint 2挂在不同环点的两点有两条路径，分别走环两侧。
Hint 3剥叶累计每个环点组大小 $size_i$。
### 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$。
Hint 1无向结构的每个函数图分量是一个环加挂树。
Hint 2挂树边任意定向都不会单独形成环。
Hint 3长度 L 的环有 $2^L$ 种定向，只排除两种全顺/全逆的有向环。
### 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) ## 扩展与联系 ## 灵活性实验室：Preserve Distinct（研究导读） ### 定位与来源 - VJudge：[AtCoder-agc062_f Preserve Distinct](https://vjudge.net/problem/AtCoder-agc062_f) - 原题：[AtCoder Grand Contest 062 F](https://atcoder.jp/contests/agc062/tasks/agc062_f) - 官方题解：[AtCoder Editorial](https://atcoder.jp/contests/agc062/editorial/6475) - 难度：AGC 2000 分；考点：随状态重建函数图、剥叶、环上相等弦的交错结构 有 $N$ 个牌堆、数字 $1..M$，每个数字恰在两个不同牌堆各出现一次，且初始各堆顶数字互异。每次只能删除一个堆顶，并要求删除后所有非空堆顶仍互异；$M\le2\times10^5$，问最多删除多少张牌。 本题保留为“灵活性实验室”，不作为本章后续硬前置。目前只给出经官方题解核对的建模主线，不提供未完成的参考实现，也不把它计作已通过质量门槛的正式例题。
观察 1：状态怎样变成函数图 当前第 $i$ 堆顶为 $a_i$，令 $p_i$ 为数字 $a_i$ 的另一张卡所在牌堆，从 $i$ 向 $p_i$ 连边。每个非空堆恰有一条出边，因此得到动态函数图。
观察 2：为什么先找入度 0 的堆 若堆 $i$ 是当前函数图的叶子（入度 0），就没有别的堆顶数字把“另一张卡”放在堆 $i$ 内。它不会成为别人的立即冲突目标，可以从叶侧持续删除并在堆顶变化后更新函数图。反复处理会清掉所有非环部分。
观察 3：环为什么还不是普通环 DP 删除某张牌会改变该堆出边，函数图本身随之变化。应截取每个环堆从当前堆顶到“前驱堆顶的另一张卡”之间的片段，再按环序拼成序列 $X$；每个数字在 $X$ 中出现零、一或两次。
观察 4：什么结构能打破环 若 $X$ 中有只出现一次的数字，或有两对位置按 $x,\ldots,y,\ldots,x,\ldots,y$ 交错，则可以选择删除顺序打破当前环，之后重新出现叶子并继续剥除。真正阻塞的是所有相等位置对都呈不交错的嵌套结构。
### 不做题也应获得的考虑链 1. **朴素状态失败。** 用每堆已删张数作状态有指数级组合；只看当前哪些数字冲突又丢失了牌堆内部顺序。 2. **第一次换对象。** 不追踪全部牌面，而让每个当前堆顶指向其副本所在堆。合法删除的传播关系因此变成函数图的叶与环。 3. **剥叶的含义变化。** 普通函数图剥叶一次就固定环；本题每次露出新堆顶后必须局部重建出边。算法维护的是“动态障碍图”，不是静态图模板。 4. **第二次换对象。** 对剩余环，把各堆关键片段拼成循环序列 $X$。问题由牌堆操作转成圆周上相等位置配对的拓扑：单次出现或交错弦能制造破口，完全嵌套才形成最终障碍。 5. **最终算法轮廓。** 栈可在线判断成对位置是嵌套还是交错，并在线枚举“沿相邻位置、再跳到相等位置”的交替环；给每个候选环累计最终必须保留的牌数，取最小值，再用总牌数减去它。官方题解给出整体 $O(M)$ 的实现方向。 ### 阅读验证与失效边界 - 最小反例是三个堆顶副本首尾相接成环，且下一张恰是前驱堆顶：任何一步都会制造两个相同堆顶，答案可以是 0。 - “叶子就整堆一次删完”是概念上的可交换性结论；实际实现仍要在每次新堆顶出现时更新其指向及相关入度。 - 每个数字恰出现两次，使相等关系成为配对；若出现三次，`另一张卡所在堆` 不再唯一，函数图与弦匹配模型同时失效。 - 当前缺口是把交替环的栈枚举、候选环权值与原牌堆下标写成一套可对拍的不变量。补齐前，本节只标研究导读，不给伪代码或附件，避免把轮廓误写成可提交算法。 ## 扩展与联系 基环树最大独立集、直径等问题通常先做挂树 DP，再在环上做断环 DP。若每个分量可能有多环，就不再是基环树，剥叶后剩余的是一般 2-core，环上链式 DP 会失效。 ## 总结与自检 1. 无向度数剥叶与函数图入度剥叶分别留下什么？ 2. 挂树大小怎样在剥叶过程中汇总？ 3. 异环组点对为什么恰有两条简单路径？ 4. 环定向为什么只排除两种？ ## 课后训练建议 用随机小函数图与 Floyd/枚举环核对剩余点；无向题枚举所有简单路径对拍。之后自行推导“基环树最大权独立集”的两次链 DP。