Score : $350$ points

问题描述

存在一个有向图，包含 $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$ 的边。
• 若 $i \neq j$，则 $B_i \neq B_j$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a directed graph with $N$ vertices and $N$ edges. The $i$-th edge goes from vertex $i$ to vertex $A_i$. (The constraints guarantee that $i \neq A_i$.) Find a directed cycle without the same vertex appearing multiple times. It can be shown that a solution exists under the constraints of this problem.

Notes

The sequence of vertices $B = (B_1, B_2, \dots, B_M)$ is called a directed cycle when all of the following conditions are satisfied:

• $M \geq 2$
• The edge from vertex $B_i$ to vertex $B_{i+1}$ exists. $(1 \leq i \leq M-1)$
• The edge from vertex $B_M$ to vertex $B_1$ exists.
• If $i \neq j$, then $B_i \neq B_j$.

Constraints

• All input values are integers.
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le N$
• $A_i \neq i$

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print a solution in the following format:

$M$

$B_1$ $B_2$ $\dots$ $B_M$

$M$ is the number of vertices, and $B_i$ is the $i$-th vertex in the directed cycle.

The following conditions must be satisfied:

• $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$ )

If multiple solutions exist, any of them will be accepted.

Sample Input 1

7
6 7 2 1 3 4 5

Sample Output 1

4
7 5 3 2

$7 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 7$ is indeed a directed cycle.

Here is the graph corresponding to this input:

Here are other acceptable outputs:

4
2 7 5 3

3
4 1 6

Note that the graph may not be connected.

Sample Input 2

2
2 1

Sample Output 2

2
1 2

This case contains both of the edges $1 \rightarrow 2$ and $2 \rightarrow 1$. In this case, $1 \rightarrow 2 \rightarrow 1$ is indeed a directed cycle.

Here is the graph corresponding to this input, where $1 \leftrightarrow 2$ represents the existence of both $1 \rightarrow 2$ and $2 \rightarrow 1$:

Sample Input 3

8
3 7 4 7 3 3 8 2

Sample Output 3

3
2 7 8

Here is the graph corresponding to this input:

update @ 2024/3/10 08:50:26