可撤销并查集求条

#include<bits/stdc++.h>
#define int long long
#define pb push_back

using namespace std;

const int N=2e5+100;

int n,m;
int opt[N],a[N],b[N];

struct DSU{
    int n=0,tot=0;
    int f[N],siz[N],s[N];

    void ins()
    {
        n++,f[n]=n,siz[n]=1;
    }//插入一个节点

    int find(int x)
    {
        if(x!=f[x]) f[x]=find(f[x]);
        return f[x];
    }//就是普通的find函数

    void merge(int x,int y)
    {
        x=find(x),y=find(y);
        if(x==y)    return;
        if(siz[x]<siz[y])   swap(x,y);
        s[++tot]=y,f[y]=x,siz[x]+=siz[y];
    }//按秩合并

    void delete_top_edge()
    {
        if(!tot)    return;
        int y=s[tot--];
        siz[f[y]]-=siz[y],f[y]=y;
    }//删除栈顶的边

    void delete_edge(int num)
    {
        while(tot>num)  delete_top_edge();
    }//只保留num条边
}dsu;

vector<int> G[N];

int t[N];
int ans[N];
void dfs(int u=0)
{
    t[u]=dsu.tot;
    if(opt[u]==1)   dsu.merge(a[u],b[u]);
    if(opt[u]==3)   ans[u]=(dsu.find(a[u])==dsu.find(b[u]));
    for(auto v:G[u])
        dfs(v);
    dsu.delete_edge(t[u]);
}

signed main()
{
    freopen("P3402_9.in","r",stdin);
    freopen("P3402_9.out2","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)   dsu.ins();
    for(int i=1;i<=m;i++)
    {
        cin>>opt[i];
        if(opt[i]==2)   cin>>a[i],G[a[i]].pb(i);
        else    cin>>a[i]>>b[i],G[i-1].pb(i);
    }
    dfs();
    for(int i=1;i<=m;i++)
        if(opt[i]==3)
            cout<<ans[i]<<endl;
    return 0;
}