并查集之游戏

题目

思路

并查集，备份原数组，去掉所有应该去掉的边，记录操作
然后从q操作到1操作倒向加边，求解

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;
int df[maxn],f[maxn];
int a[maxn][2];
int n;
int find_root(int x,int num){
    if(num>n)return f[x]=0;
    if(x==f[x])return x;
    return f[x]=find_root(f[x],num+1);

}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        if(x!=0)df[i]=f[i]=x;
    }
    int q;scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&a[i][0],&a[i][1]);
        if(a[i][0]==2){
            f[a[i][1]]=a[i][1];
        }
    }
    for(int i=q;i>=1;i--){
        if(a[i][0]==1){
            a[i][1]=find_root(a[i][1],0);
        }
        else{
            f[a[i][1]]=df[a[i][1]];
        }
    }
    for(int i=1;i<=q;i++){
        if(a[i][0]==1){
            if(a[i][1])printf("%dn",a[i][1]);
            else printf("CIKLUSn");
        }
    }
}