(用树结构支持并查集8.2.2)POJ 1703 Find them, Catch them(并查集的简单使用: 判断两个元素是否属于同一集合)

/*
 * POJ_1703.cpp
 *
 *  Created on: 2013年11月5日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 100000;

int set[maxn*2+10];

int set_find(int p){//并查集的查找过程
	if(set[p] < 0){
		return p;
	}
	return set[p] = set_find(set[p]);
}


int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		memset(set,-1,sizeof(set));//开始时,每个罪犯都是一个集合
		int n,m;
		scanf("%d%d",&n,&m);

		char str[15];
		int a,b;
		int i;
		for(i = 0 ; i < m ; ++i){

			scanf("%s %d %d",str,&a,&b);
			if(str[0] =='A'){
				//如果a与b不是同一帮派&&a与b的另一个帮派也不是同一个帮派
				if(set_find(a) != set_find(b) && set_find(a) != set_find(b+n)){
					printf("Not sure yet.\n");
				}else if(set_find(a) == set_find(b)){//如果a与b属于同一个帮派
					printf("In the same gang.\n");
				}else{
					printf("In different gangs.\n");
				}
			}else{
				if(set_find(a) != set_find(b+n)){
					set[set_find(a)] = set_find(b+n);//将a的帮派设为b的另外一个帮派
					set[set_find(b)] = set_find(a+n);
				}
			}
		}
	}

	return 0;
}