# 滴嘟hia的能指循环：足够远的终点

出题人解法：对出边映射倍增，再统计不同终点。Codex（GPT-6）：按输入规模选择轮数，用顶点标记替代排序去重。程序 [alternative-doubling.cpp](alternative-doubling.cpp) 是[路径法](solution.zh.md)的备用方案，通过完整正式数据。

令 $f(v)=d_v$ .初始数组保存 $f(v)$ ，并记当前步数为一。若步数仍小于 $n$ ，用一个独立缓冲数组计算每个顶点的“终点的终点”，交换数组，再将步数乘二。结束时得到 $f^q(v)$ ，其中 $q$ 是不小于 $n$ 的二的幂。统计这些终点中的不同顶点数。

走至少 $n$ 步后，任意起点都已进入某个环，所以所有终点都在环上。另一方面，限制在一个环上的 $f^q$ 是循环排列，每个环顶点都恰好是某个环内起点的终点。因此终点集合恰为全部环顶点，去重计数正确。

每轮同时基于旧数组更新，不能原地逐项覆盖。轮数为 $O(\log(n+1))$ ，总时间 $O(n\log(n+1)+1)$ ，空间 $O(n+1)$ .结束后的去重使用按编号索引的布尔数组，耗时线性。$n=0$ 时两段循环都为空，输出零。

倍增展示了从映射的像集识别环的思路，也可扩展到查询远距离后继，但本题只求环顶点总数，线性方法的时间界更好。

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