poj 1703 find them,catch them

這個題目是典型的種類判斷的並查集，種類判斷的並查集似乎無一例外的全部用到了relation（與祖先的關系），然後就是找關系化簡式子然後套用種類判斷並查集的通常做法就好。這個題目就是告訴你，現在一個城市裡面有兩個幫派，任何一個幫派分子不是屬於這個幫派就是屬於另一個幫派。現在告訴你現在有多少幫派分子，然後有m句話，其中A開頭的表示詢問這兩個人的關系如何，D是告訴你這兩個人不是一伙的。附代碼。

[cpp]
<SPAN style="FONT-SIZE: 18px">#include<iostream> 
#include<stdio.h>  
using namespace std; 
int father[100000+10]; 
int relation[100000+10]; 
int flag; 
int find_ant(int x) 
{ 
    if(x!=father[x]) 
    { 
        int temp=father[x];; 
        father[x]=find_ant(father[x]); 
        relation[x]=(relation[x]+relation[temp])%2; 
    } 
    return father[x]; 
} 
void unin(int x,int y) 
{ 
    int x_x,y_y; 
    x_x=find_ant(x); 
    y_y=find_ant(y); 
    if(x_x!=y_y) 
    { 
        father[y_y]=x_x; 
        relation[y_y]=(relation[x]+relation[y]+1)%2; 
    } 
    else { 
        if(relation[x]==relation[y]) 
            flag=1; 
        else flag=0; 
    } 
} 
int main() 
{ 
    int T,a,b,n,m,i,p,q; 
    char c; 
    cin>>T; 
    while(T--) 
    { 
        cin>>n>>m; 
        for(i=1;i<=n;i++) 
        { 
            father[i]=i; 
            relation[i]=0; 
        } 
        for(i=1;i<=m;i++) 
        { 
            getchar(); 
            c=getchar(); 
            scanf("%d%d",&a,&b); 
            if(c=='A') 
            { 
                p=find_ant(a); 
                q=find_ant(b); 
                if(p!=q) 
                    cout<<"Not sure yet."<<endl; 
                else { 
                    unin(a,b); 
                    if(flag==1) 
                        cout<<"In the same gang."<<endl; 
                    else cout<<"In different gangs."<<endl; 
                } 
            } 
            else if(c=='D') 
            { 
                unin(a,b); 
            } 
        } 
    } 
    return 0; 
} 
 
</SPAN> 

#include<iostream>
#include<stdio.h>
using namespace std;
int father[100000+10];
int relation[100000+10];
int flag;
int find_ant(int x)
{
 if(x!=father[x])
 {
  int temp=father[x];;
  father[x]=find_ant(father[x]);
  relation[x]=(relation[x]+relation[temp])%2;
 }
 return father[x];
}
void unin(int x,int y)
{
 int x_x,y_y;
 x_x=find_ant(x);
 y_y=find_ant(y);
 if(x_x!=y_y)
 {
  father[y_y]=x_x;
  relation[y_y]=(relation[x]+relation[y]+1)%2;
 }
 else {
  if(relation[x]==relation[y])
   flag=1;
  else flag=0;
 }
}
int main()
{
 int T,a,b,n,m,i,p,q;
 char c;
 cin>>T;
 while(T--)
 {
  cin>>n>>m;
  for(i=1;i<=n;i++)
  {
   father[i]=i;
   relation[i]=0;
  }
  for(i=1;i<=m;i++)
  {
   getchar();
   c=getchar();
   scanf("%d%d",&a,&b);
   if(c=='A')
   {
    p=find_ant(a);
    q=find_ant(b);
    if(p!=q)
     cout<<"Not sure yet."<<endl;
    else {
     unin(a,b);
     if(flag==1)
      cout<<"In the same gang."<<endl;
     else cout<<"In different gangs."<<endl;
    }
   }
   else if(c=='D')
   {
    unin(a,b);
   }
  }
 }
 return 0;
}