分数: 350 点
问题陈述
有一个有向图 N 顶点和 N 边缘。
的 i- 第一条边从顶点出发 i 到顶点 A_i。 (约束条件保证 i \neq A_i.)
找到一个没有相同顶点多次出现的有向循环。
可以证明,在该问题的约束下存在解。
注释
顶点序列 当满足以下所有条件时, B = (B_1, B_2, \dots, B_M) 称为有向循环:
- M \geq 2
- 顶点的边 B_i 到顶点 B_{i+1} 存在。 (1 \leq i \leq M-1)
- 顶点的边 B_M 到顶点 B_1 存在。
- If i \neq j,那么 B_i \neq B_j.
约束
- 所有输入值均为整数。
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le N
- A_i \neq i
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
按以下格式打印解决方案:
M B_1 B_2 \dots B_M
M 是顶点数,并且 B_i 是 i有向循环中的第一个顶点。
必须满足以下条件:
- 2 \le M
- B_{i+1} = A_{B_i} ( 1 \le i \le M-1 )
- B_{1} = A_{B_M}
- B_i \neq B_j ( i \neq j )
如果存在多个解决方案,则将接受其中任何一个。
示例输入 1
7 6 7 2 1 3 4 5
示例输出 1
4 7 5 3 2
7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7 确实是一个有向循环。
这是与此输入对应的图表:

以下是其他可接受的输出:
4 2 7 5 3
3 4 1 6
请注意,图形可能未连接。
示例输入 2
2 2 1
示例输出 2
2 1 2
这种情况包含两条边 1 \rightarrow 2 和 2 \rightarrow 1.
在这种情况下, 1 \rightarrow 2 \rightarrow 1 确实是一个有向循环。
这是与此输入对应的图表,其中 1 \leftrightarrow 2 代表两者都存在 1 \rightarrow 2 和 2 \rightarrow 1:

示例输入 3
8 3 7 4 7 3 3 8 2
示例输出 3
3 2 7 8
这是与此输入对应的图表:
