POJ 1703

• 此题2种情况，一种情况是确定种类不同,另一种就是询问同类的关系
• 注意scanf()读取
• 还是开一个数组rala[]记录该点与父节点的关系，1表示不同类,0表示同类,在路径压缩到根节点的同时，每一步都进行 该点rala[i]与父节点rala[pre[i]]关系异或rala[i]^rala[pre[i]],这样能使关系保持相同，并且每点只想根节点,
• 询问就是 判断根节点是否相同，不同则无法确定，（找根节点时已经路径压缩了）相同在判断2点与根节点的关系，

  #include <iostream>
  #include <cstring>
  using namespace std;
  const int maxn = 1e5+10;
  int pre[maxn];
  int rala[maxn];
  void init(int n) {
  	memset(rala,0,sizeof rala);
  	for (int i=1; i<=n; i++) pre[i] = i;
  }
  int find(int x) {
  	int temp = pre[x];
  	if (x == pre[x]) return x;
  	pre[x] = find(pre[x]); // 先继续找下去，会使的根部的rala[]初始化
  	//路径压缩的同时压缩x 与 根节点的关系,
  	rala[x] = rala[x] ^ rala[temp];
  	return pre[x];
  }
  void merge(int a,int b) {
  	int ra = find(a);
  	int rb = find(b); // rala[] 路径压缩成功
  	if (ra == rb) return ;
  	pre[ra] = rb;
  	// 已知两点属于不同类
  	// 通过a,b与各自ra,rb的关系推倒ra与rb的关系
  	rala[ra] = (rala[a] + rala[b] +1)%2;
  }
  int test,n,m;
  int main() {
  //	freopen("a.txt","r",stdin);
  	
  	scanf("%d",&test);
  	while (test--) {
  		scanf("%d%d",&n,&m);
  		init(n);
  		
  		for (int i=1; i<=m; i++) {
  			int u,v;
  			char ch;
  			scanf("\n%c%d%d",&ch,&u,&v);
  			if (ch == 'A') { //关系不确定，需要自己查询,
  				// 判断他们根节点之间的关系
  				int ra = find(u);
  				int rb = find(v);
  				if (ra == rb) {//根节点相同有两种关系，同类和不同类
  					if (rala[u] ^ rala[v]) { //不同类
  						printf("In different gangs.\n");
  					}
  					else { // 同类
  						printf("In the same gang.\n");
  					}
  				}
  				else {// 根节点不同则无法确定两点之间的关系
  					printf("Not sure yet.\n");
  				}
  			}
  			else { //关系确定，且a,b属于不同的种类
  				// 在merge中判断根节点是否相同
  				merge(u,v);
  			}
  		}
  	}
  	return 0;
  }