滴嘟hia的能指循环:递增访问时间戳¶
出题人解法,见配套讲解。Codex(GPT-6):整理当前行走的判定证明和标准实现。alternative-timestamps.cpp 与当前路径法并列,通过完整正式数据。
每个未访问顶点的时间戳为零,全局计数器从一开始。开始一次新行走时,记录计数器值 \(b\) .沿出边走,每首次遇到一个顶点就写入当前计数器并将计数器加一。
到达已有时间戳 \(t\) 的顶点时,若 \(t\ge b\) ,它在本次行走中出现,环长为当前计数器减去 \(t\) ;若 \(t<b\) ,则已进入此前处理的区域。起点已访问时直接跳过。
全局时间戳严格递增,之前行走的所有时间戳都小于 \(b\) ,本次行走的时间戳都不小于它,因此判定准确。当前路径按连续序号编号,重复顶点到路径末尾的元素数量正好是两序号之差。其余正确性与唯一出边形成路径和环的性质一致。
每个顶点只赋值一次,总时间 \(O(n+1)\) 、空间 \(O(n+1)\) .只需出边数组、时间戳数组及常数个变量,省去显式路径、位置清理和额外访问数组。计数器至多 \(n+1\) ,在本题范围内普通整数足够。