题解 CF1095D Circular Dance

我们令 $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}$

#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);
}

Dilute

题解 CF1095D Circular Dance