(POJ) Find them, Catch them

http://poj.org/problem?id=1703

先開一個2*MAX_N的disjoint set，其中1~MAX_N是在第一個幫派的可能，MAN_N + 1 ~ MAX_N + MAX_N 是第二個幫派的可能，那麼，當做到D操作時，可以合併[A],[B] + MAX_N和 [A] + MAX_N, [B]，那查詢的時候，可以依照這個樣子去查，就okay囉！

時間複雜度：O(alpha(N))

#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_N = 1e5 + 3;

struct DisjointSet {
 int p[2 * MAX_N];
 void init(int i){
  for (int x=0;2*MAX_N>x;x++) {
   p[x]=x;
  }
 }
 int Find(int x) {
  return p[x]==x?x:p[x]=Find(p[x]);
 }
 void Union(int x,int y) {
  p[Find(x)]=Find(y);
 }
} djs;

int main() {
 int T;
 scanf("%d",&T);
 while (T--) {
  int n,m;
  scanf("%d %d",&n,&m);
  djs.init(n);
  for (int x=0;m>x;x++) {
   char a;
   int b,c;
   scanf("\n%c %d %d",&a,&b,&c);
   if (a=='A') {
    if (djs.Find(b) == djs.Find(c)) {
     puts("In the same gang.");
    }
    else if (djs.Find(b) == djs.Find(c+MAX_N)) {
     puts("In different gangs.");
    }
    else {
     puts("Not sure yet.");
    }
   }
   else {
    djs.Union(b,c+MAX_N);
    djs.Union(c,b+MAX_N);
   }
  }
 }
}