BISHI98　谍中谍中谍中谍中谍...¶

中等通过率 62.29%python3样例通过牛客 AC

一句话

功能图上，从每个起点出发第一个被重复访问的点是谁。

解题思路¶

这题考什么¶

功能图（每点出度恰为 1） 的结构。从任意点出发一直走 i -> p_i，路径形如一条「尾巴 + 一个环」的 ρ 形。第一个被重复访问到的点，正是这条路径进入环的那个点（环入口）：在进环之前每个点都是新的，进环后绕一圈回到入口才第一次撞车。

等价的递推刻画：

若 a 本身在环上，答案就是 a；
否则 ans[a] = ans[p_a]（尾巴上的点和它的后继走到同一个环入口）。

数据规模与复杂度¶

n <= 1000。直接对每个起点模拟走一遍是 O(n^2) = 1e6，完全够用而且最不容易写错，本解就用它。（若 n 到 1e5，就应改用上面的递推或 Floyd 判环，那是 O(n)。）

Python 的坑¶

每个起点都要一份「本轮是否访问过」的标记。反复 new 一个长度 n 的数组会产生 1000 次分配，用时间戳染色（stamp 数组存轮次编号）可以只分配一次、O(1) 重置，常数更优；
模拟循环是纯迭代，不涉及递归，没有深度问题；
输出是一行 n 个整数，用 " ".join 拼好一次写出。

坑在哪¶

「第一次给已被警告过的学生再次警告」——注意起点自己也算被警告过一次，所以自环 p_a = a 时答案就是 a；
输出的第 a 个数对应起点 a，别把下标搞成 0-based。

样例复核¶

p = [2,3,1]。起点 1：1->2->3->1，1 是第一个重复的 -> 1；起点 2 -> 2；起点 3 -> 3。输出 "1 2 3"，与样例一致。

参考实现¶

solutions/BISHI98.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    p = [0] + [int(v) for v in data[1:1 + n]]      # 1-based

    stamp = [0] * (n + 1)                          # 时间戳染色，避免反复重建数组
    ans = [0] * (n + 1)
    for a in range(1, n + 1):                      # 依次把每个学生当作起点模拟一遍
        u = a
        while stamp[u] != a:                       # 直到撞上本轮已访问的点
            stamp[u] = a                           # 用起点编号 a 兼作本轮的时间戳
            u = p[u]                               # 功能图上每点只有一条出边
        ans[a] = u                                 # 第一个被重复访问的点 = 环入口
    sys.stdout.write(" ".join(map(str, ans[1:])) + "\n")   # 第 a 个数对应起点 a


main()

BISHI98 谍中谍中谍中谍中谍...¶