1 #include<cstdio> 2 #include<ext/rope> 3 using namespace std; 4 using namespace __gnu_cxx; 5 rope<int> *fa[20001]; 6 int a,b,n,m,A[20001],op; 7 int Root(int num,int x) 8 { 9     if(fa[num]->at(x)==x)10       return x;11     int rt=Root(num,fa[num]->at(x));12 //      if(rt==fa[num]->at(x))若不加这两行，bzoj3674会爆内存。13 14 //     return rt;15         fa[num]->replace(x,rt);16         return rt;17 }18 void Union(int num,int x,int y)19 {20     int U=Root(num,x),V=Root(num,y);21     fa[num]->replace(V,U);22 }23 int main()24 {25     scanf("%d%d",&n,&m);26     for(int i=1;i<=n;i++)27       A[i]=i;28     fa[0]=new rope<int>(A,A+n+1);29     for(int i=1;i<=m;i++)30       {31           fa[i]=new rope<int>(*fa[i-1]);32           scanf("%d",&op);33           if(op==1){scanf("%d%d",&a,&b);Union(i,a,b);}34           else if(op==2){scanf("%d",&a);fa[i]=fa[a];}35           else{scanf("%d%d",&a,&b);printf("%d\n",Root(i,a)==Root(i,b));}36       }37     return 0;38 }