# 滴嘟hia的能指循环：追踪当前路径

出题人解法：沿出边行走，用当前路径的位置标记识别新环；讲解中还包含时间戳和倍增方法。Codex（GPT-6）：修复输入辅助函数、整理迭代实现及证明，并补充入度剥离方案。

## 首选算法

维护全局已访问标记，以及顶点在当前路径中的位置，后者初始为 $-1$ .依次选择未访问顶点作为起点，沿唯一出边前进：每到一个新顶点，把它加入路径，记录位置并标记已访问。

遇到已访问顶点 $v$ 时停止。若它仍有当前路径位置 $p$ ，则从位置 $p$ 到路径末尾构成一个环，长度为 $|P|-p$ ，加入答案。若它不在当前路径中，则这次行走汇入已处理的部分，无须增加答案。最后清除本次路径的位置标记，保留全局访问标记。

## 正确性

在有限图中不断沿唯一出边前进，最终必然重复一个顶点。停止前当前路径的顶点互不相同。若重复的是当前路径中的顶点，则其后缀首尾相接，且后缀内部没有重复，恰为一个环；前缀仅通向该环。若重复的是先前路径中的顶点，则后续走向完全由出边确定，所有可能遇到的环已由之前处理。

每个顶点只会首次加入一条路径，且每个新环只在首次进入其所属部分时被发现，因此不会漏计或重复计数。自环形成长度为一的后缀；空图循环不执行，答案为零。

## 复杂度与方案比较

每个顶点至多入路径、清除位置各一次，时间 $O(n+1)$ ，空间 $O(n+1)$ .程序用显式路径数组，避免长链造成线性深度的递归调用。

[std.cpp](std.cpp) 保留当前路径方案。以下程序均有完整说明，并通过全部正式数据：

- [时间戳](solution-alternative-timestamps.zh.md)，[源码](alternative-timestamps.cpp)：出题人已有方案，以全局递增访问序号区分本次路径，省去路径数组和独立访问标记，作为并列方案。
- [入度剥离](solution-alternative-pruning.zh.md)，[源码](alternative-pruning.cpp)：Codex（GPT-6）应用零入度删除，线性时间计算剩余顶点数，是结构不同的补充方案。
- [倍增后统计像集](solution-alternative-doubling.zh.md)，[源码](alternative-doubling.cpp)：出题人已有思路，时间 $O(n\log(n+1)+1)$ ，作为备用。Codex 根据规模选择轮数，并用标记代替排序统计不同终点。

时间戳确实减少了本实现维护的数组，但当前各程序实测的微小时间差不构成稳定加速结论。数据包含十万顶点长链、大环、全自环、多环及随机重编号。

测试配方见 [plan.json](tests/plan.json)，生成方式见[数据生成说明](../../../README.md#使用题目文件)。参考环境、逐次测量和适用范围见[评测说明](../../../docs/评测环境与性能.md)。