我们令$fa[i]$为$i$直接连向的点

那么显然,$fa[i] \in {a_{i, 1}, a_{i, 2}}​$

假设$a_{i, 1}$为$fa[i]$,那么$a_{2, i} \in { a_{fa[i], 1}, a_{fa[i], 2} }$

否则肯定有$a_{2, i} \not\in { a_{fa[i], 1}, a_{fa[i], 2} }$

所以,如果有$a_{2, i} \in { a_{fa[i], 1}, a_{fa[i], 2} }$,那么$fa[i] = a_{i, 1}$,否则$fa[i] = a_{i, 2}$

按照这个模拟即可

接下来送上代码

最后还有一点

n = 3的时候上述方法是不适用的。

但是显然,n = 3 的时候随便输出一个环都能是答案

但是用这个方法可能构造出一个$n \leq 2$的环……

反正这个特判不加会$\color{red}\text{WA on test 13}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>

#define INF 2147483647
#define ll long long

inline int inp(){
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}

int a1[200010];
int a2[200010];
int fa[200010];

inline bool rel(int a, int b){ // 判断b是否有 b ∈ { a_{a1}, a_{a2} }
return (b == a1[a] || b == a2[a]);
}

int main(){
int n = inp();
if(n == 3){
printf("1 2 3");
return 0;
}
for(int i = 1; i <= n; i++){
a1[i] = inp();
a2[i] = inp();
}
for(int i = 1; i <= n; i++){
if(rel(a1[i], a2[i]))
fa[i] = a1[i];
else
fa[i] = a2[i];
}
int cur = 1;
while(fa[cur] != 1){
printf("%d ", cur);
cur = fa[cur];
}
printf("%d\n", cur);
}

 评论