← 返回题目列表

AtCoder · abc311_c

E. 找到它!

中文机器翻译题面 查看原题

分数: 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

这是与此输入对应的图表: