④处应该填( )
一个有向图中有 n 个顶点 (n <= 1000),编号从 1 到 n,每个顶点的出度有且只有 1 个,用 nxt[i] 表示。输出图中所有环上的顶点编号,每个环输出一行。先输出编号更小的顶点能够到达的环,每个环从环内编号最小的结点开始输出。 输入描述: 第一行输入包含一个整数 n,表示图中的顶点数量。 第二行输入 n 个整数,表示第 i 个顶点的唯一后驱顶点 nxt[i]。 输出描述: 输出若干行,每行表示一个环上的顶点编号。先输出编号更小的顶点能够到达的环,每个环从环内编号最小的结点开始输出。 样例输入:
>4
2 3 4 2
样例输出:
>2 3 4
#include <bits/stdc++.h>
using namespace std;
int n, fast, low, nt;
int nxt[1005];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &nxt[i]);
for(int i = 1; i <= n; i++){
if(nxt[i]){
low = fast = i;
do{
low = nxt[low];
fast = nxt[nxt[fast]];
}while( ① );
int minnode = fast;
do{
fast = nxt[fast];
minnode = min(minnode, fast);
}while( ② );
fast = minnode;
while( ③ ){
nt = nxt[fast];
printf("%d ", fast);
nxt[fast] = ④;
⑤,
}
if (fast) printf("\n");
}
}
return 0;
}
A. 1
B. low
C. nt
D. 0