基环树中环节点通过拓扑排序（有向）或并查集/DFS回边（无向）识别，环外树需反向建图并从环节点BFS遍历，环序须单独提取以支持DP等操作。
怎么识别基环树里的环和环外树
基环树本质是「一个环 + 若干棵挂在环上节点的有向树（或无向树）」，关键在区分哪些节点属于环、哪些属于环外树。最稳的办法是用 DFS 或 拓扑排序 判环 + 标记：对无向图，常用并查集或 DFS 回边；对有向图，必须用入度拓扑或 DFS 状态标记（unvisited/visiting/visited）。
常见错误是直接从任意点 DFS 一次就认为「第一次遇到的回边终点到当前点就是环」——这在多叉分支下容易漏判或截断环。正确做法是：先用拓扑排序把所有树边上的节点（即入度可减至 0 的节点）全部剥离，剩下没被剥离的节点一定全在环上或环的强连通分量里。
- 无向基环树：用并查集边加边判断是否成环；或 DFS 记录父节点，遇到非父已访问节点即为环边，再沿 parent 回溯还原环节点
- 有向基环树：建图后跑一遍拓扑排序，剩余
indegree > 0的节点集合就是环上节点（每个节点入度至少为 1，且构成唯一环） - 注意：基环树默认只有一个环，但代码里不能假设「只剩一个连通块」，要对每个连通分量单独处理
如何安全地遍历环外树（不误入环）
环外树的根一定在环上，叶子是入度为 0（有向）或度为 1（无向）的节点。处理环外部分时，绝不能从环节点出发盲目 DFS——可能绕回环内。正确做法是「反向建树」或「限制遍历方向」。
例如有向基环树中，原图边是 u → v，环外树结构是「指向环」的，那么环外部分实际是「以环为汇点的 DAG」。此时应反向建图（v → u），从环上每个节点出发 BFS/DFS，这样只访问其子树（即原图中指向它的那部分树），天然隔离环本身。
立即学习“C++免费学习笔记（深入）”；
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 无向图：在识别出环节点集合
in_cycle后，对每个环节点c，做 BFS，但禁止将任何in_cycle[node] == true的邻居加入队列 - 有向图（环外边指向环）：反向图 + 从环节点开始 BFS，访问到的就是整个环外树（原图中的「上游」）
- 别忘了清空 visited 标记——环节点在环处理阶段和树处理阶段需复用同一数组，但语义不同，建议拆成
in_cycle[]和tree_visited[]
环上节点单独处理时要注意什么
环是一串首尾相连的节点，不是链表也不是普通图。直接按输入顺序遍历会错乱；靠邻接表随机取邻居可能跳步。必须先抽取出环的「有序序列」，即顺时针或逆时针走一圈得到的节点列表。
怎么抽？对无向环，在 DFS 找到回边 (u, v) 后，用 parent 数组从 u 和 v 分别往上跳，直到相遇，再拼出环；对有向环，拓扑后剩的节点还需重建环序：任取一环节点，顺着原图出边走，每步都确保下一节点也在环内（查 in_cycle），走 len 步必回到起点，中间路径就是环序。
- 环长可能为 2（有向图中两个节点互指），此时
next[next[x]] == x，别写死成「至少 3 个点」 - 环上做 DP（如最大权独立集）时，要拆成「选首节点」和「不选首节点」两个线性链分别跑，否则环形依赖无法递推
- 别在环上用
std::vector::erase动态删点——顺序会变，建议用索引或新建数组存环节点
一个典型错误：把环外树当成森林重复初始化
基环树整体是一棵树加一条边，但环外部分可能是多棵子树挂在同一个环节点上。有人会为每个环节点新建一个 visited 数组或重置 DP 状态，导致时间复杂度飙升（O(n²)）。
正确方式是全局一套 visited，并在进入每棵环外树前，用栈或 vector 记录本次 BFS/DFS 访问了哪些节点，结束后统一标记（比如设为 tree_id[i] = cid），避免重复访问，也不用反复 memset。
- 尤其注意：环上节点虽然属于环，但它也是某棵环外树的根，所以它的「树属性」和「环属性」是正交的，不要因为它是环节点就跳过对其子树的处理
- 如果题目要求统计每棵环外树大小，别用
size = 0; dfs(root);然后返回——环节点 root 本身不算在树大小里（它是环的一部分），只算它的真子树节点 - 调试时打印
in_cycle和tree_root映射关系，比看最终答案更容易定位挂错树的问题
环序提取和树/环边界判定是整个流程最易出错的地方，稍不注意就会把一个环节点当成树叶子，或者把树边当成环边。动手前先手画三节点环加两棵单节点子树，跑一遍逻辑，比写十行代码还管用。
