Find it!

题目描述

有一个有向图，包含 $N$ 个顶点和 $N$ 条边。
第 $i$ 条边从顶点 $i$ 指向顶点 $A_i$。（约束保证 $i \neq A_i$。）
找出一个没有重复顶点出现的有向环。
可以证明在本题的约束下至少存在一个解。

Notes

当满足以下所有条件时，顶点序列 $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$ 的边。 若 $i \neq j$，则 $B_i \neq B_j$。

输入格式

输入由标准输入按以下格式提供： $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$ )

若存在多个解，任意一个都将被接受。

7
6 7 2 1 3 4 5

4
7 5 3 2

4
2 7 5 3

3
4 1 6

2
2 1

2
1 2

8
3 7 4 7 3 3 8 2

3
2 7 8

提示

所有输入值均为整数。 $2 \le N \le 2 \times 10^5$ $1 \le A_i \le N$ $A_i \neq i$$7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7$ 确实是一个有向环。 下面是对应于该输入的图： 以下是其他可接受的输出：

注意图可能不是连通的。
此例同时包含边 $1 \rightarrow 2$ 和 $2 \rightarrow 1$。
在这种情况下，$1 \rightarrow 2 \rightarrow 1$ 确实是一个有向环。 下面是对应于该输入的图，其中 $1 \leftrightarrow 2$ 表示同时存在 $1 \rightarrow 2$ 和 $2 \rightarrow 1$：
下面是对应于该输入的图：

标签: AtCoder|abc311C

来源

AtCoder|abc311C