学步园

【转】

解析：并查集的题目，并查集的拓展。一般的思路是先初始化，各个数自成一个组，然后是两个gangs自成一个组，但由于两个给定元素有三种关系: In
the same gang;  In
different gangs;  Not
sure
yet;
采用此模型的缺点是判断两个元素关系还未确定这种情况比较复杂，故模型需要改进。本题的正确模型是将已经确定关系的元素组成一个集合，然后利用两个元素的
father是同一个来确定这两个元素之间的关系。father[a]中存放的是a的根结点，rank中存放的是father[a]与a的关系，0表示两
者不在同一个gangs中，1表示两者在同一个gangs中。具体的程序还是沿袭了并查集的Make_Set（）、Find_Set()、
Union_Set()的三步骤。

心得：并查集有三步是必须的：Make_Set（）、Find_Set()、Union_Set()。

 rank[a]的改变是伴随着father[a]的改变而更新的（有father改变就有rank改变），要是father改变了，而rank未改变，此时的rank就记录了一个错误的值，father未改变（即使实际的father已不是现在的值，但只要father未改变，rank
的值就是“正确”的，认识到这点很重要。），第一次错误就是因为没有考虑清楚这点。

#include<iostream>
#include<cstdio>

using namespace std;

int father[100000+10];   //表示x的根结点 
int rank[100000+10];


void Make_Set(int n){
int i;
for(i=1;i<=n;i++){
       father[i] = i; 
       rank[i] = 1;                 
    }
}

int Find_Set(int a){
if(a==father[a])  
return a;
else {
int temp = father[a];
       father[a] = Find_Set(father[a]);   
       rank[a] = (rank[temp]+rank[a]+1)%2 ; 
//必须有，更新路径压缩之后a与根结点之间的关系； father改变，rank就必须要跟着改变 
     } 
return father[a];
}

void Union_Set(int a,int b){
int fa,fb;
     fa = Find_Set(a);
     fb = Find_Set(b);
if(fa!=fb){
         father[fa] = fb;   
         rank[fa] = (rank[a]+rank[b])%2 ;     //fa结点以下的结点的rank不需要改               
     }
}

int main(){
//freopen("1in.txt","r",stdin);
//freopen("1out.txt","w",stdout);
    int T,N,M;
char ch;
int a,b,fa,fb;
    scanf("%d",&T);
while(T--){
       scanf("%d%d",&N,&M);
       Make_Set(N);
int i;
for(i=1;i<=M;i++){
           getchar();
           scanf("%c%d%d",&ch,&a,&b);
if(ch=='A'){
if(Find_Set(a)==Find_Set(b)){           
//在使用rank之前，已经在用Find_Set函数寻找a的时候将a路径上的所有结点的rank值改变过了 
                   if((rank[a]+rank[b])%2==0){      
                      printf("In the same gang.\n");                           
                   }           
else
                      printf("In different gangs.\n");
               }  
else{
                  printf("Not sure yet.\n");     
               }

           }        
else{
              Union_Set(a,b);
           }     

       }  

    }   
return 0;
}