并查集撤销操作

并查集撤销操作

路径压缩会破坏原本的树结构，使得删除操作变得困难,所以使用按秩合并。
有n个元素，将点x从他当前所在的集合中分离，可以建立一个新的点idx=n++,将fa[x]=idx。

#include<bits/stdc++.h>
#define MAXN 200100
using namespace std;
int n,m;
int rk[MAXN],fa[MAXN];
int x,y,z;
int find(int x){//循环找爹
    while(x!=fa[x]){
        x=fa[x]=fa[fa[x]];
    }
    return x;
}

int ix=n;

void del(int x){//撤销
    fa[x]=ix;
    fa[ix]=ix;
	ix++;
}

void merge(int x,int y){//按秩合并
	x=find(x);y=find(y);
	if(x==y)return ;
	if(rk[x]<=rk[y]){
        fa[x]=y;
        return;
    }
    else{
        fa[y]=x;
        return ;
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        rk[i]=0;
        fa[i]=i;
    }
    int op,x,y;
    for(int i=1;i<=m;i++){
        cin>>op>>x;

        if(op==1){//合并
            cin>>y;
            merge(x,y);        
        }

        if(op==2){//撤销
            del(x);
        }
        if(op==3){
            cin>>y;
            if(find(x)==find(y)){//查找两个元素是否在同一个集合
                cout<<"y";
            }
            else{
                cout<<"n";
            }
            cout<<endl;
        }                                                                   
     }
    
    return 0;
}