POJ 1703 Find them, Catch them

問題

解法
union-findを使う。
人数の2倍の大きさのUF木を作って、
「AとBが違う」を unite(a, b+N), unite(a + N, b) とする。
A,Bが同じ根を持つなら同じグループ、A,B+Nが同じ根を持つなら違うグループとなり
どちらでもない場合は「まだ分からない」となる。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 100000;
int uf[MAX_N * 2];
int N, M;
void init(){
	for(int i = 0; i < N * 2; i++) uf[i] = i;
}
int root(int p){
	if(uf[p] == p) return p;
	return uf[p] = root(uf[p]);
}
bool is_same(int p, int q){
	int t = root(p);
	int s = root(q);
	return (root(p) == root(q));
}
void unite(int p, int q){
	uf[root(p)] = root(q);
}

int main(){
	int T;
	scanf("%d", &T);
	for(int i = 0; i < T; i++){
		scanf("%d %d", &N, &M);
		init();
		for(int i = 0; i < M; i++){
			char c;
			int a, b;
			scanf("%c", &c);
			scanf("%c %d %d", &c, &a, &b);
			a--; b--;
			if(c == 'D'){
				unite(a, b + N);
				unite(a + N, b);
			}else if(c == 'A'){
				if(is_same(a, b)){
					puts("In the same gang.");
				}else if(is_same(a + N, b)){
					puts("In different gangs.");
				}else{
					puts("Not sure yet.");
				}
			}
		}
	}
}