POJ(PKU) 1703 Find them, Catch them

union find

参考にさせていただきました。
http://d.hatena.ne.jp/sndr/20121221/1356071878

#include <cstdio>
#include <iostream>

using namespace std;

int par[200003];//親
int rank[200003];//木の深さ

void init(int n){
  for(int i = 0;i < n;i++){
    par[i] = i;
    rank[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  
  if(rank[x] < rank[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank[x] == rank[y])rank[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}
  
  
  
  

int main(){
  
  int g;
  scanf("%d",&g);
  
  while(g--){
  
  int n,m;
  
  scanf("%d%d",&n,&m);
  
  init(n*2);
  
  for(int i = 0;i < m;i++){
    char t;
    scanf("%c",&t);
    scanf("%c", &t);
 //   cin >> t;
    if(t == 'D'){
      int a,b;
      
      scanf("%d%d",&a,&b);
      a--; b--;
      
      unite(a,b+n);
      unite(a+n,b);
      
    }else{
      int a,b;
      
      scanf("%d%d",&a,&b);
      a--; b--;
      
      if(same(a,b)){
	printf("In the same gang.\n");
      }else if(same(a+n,b)){
	printf("In different gangs.\n");
      }else{
	printf("Not sure yet.\n");
      }
    }
  }
  }
  return 0;
  
  
}