POJ-1703 Find them, Catch them

题目链接：http://poj.org/problem?id=1703

题目大意：

在Tadu城市里面有2个犯罪团伙，罪犯都属于这两个团伙。现在给你2个罪犯，判断他们是不是一个犯罪团伙。如果当前关系不确定，就输出not sure yet.

解题思路：

并查集的应用，很A bug's life基本一样。。。。秒之。

但纠结了半个小时的地方竟然是输出看错了，同一个团伙是gang，不是gangs。。。悲剧死！~~~~~~~~

注意：

这道题数据有问题，题目中说了And of course, at least one of them belongs to Gang Dragon, and the same for Gang Snake.意思是罪犯至少有一个属于Dragon，至少有一个属于Snake，也就是说当罪犯有2个人时，肯定是不同团伙的。。。但是我测试了一下，输出not sure yet也AC了。反正看题要仔细吧。自己出题时，数据一定要考虑特殊情况，要不然会出现BUG。。。。。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define N 100010

struct node
{
	int parent;
	int relation;
}p[N];

int find(int x)
{
	int temp;
	if(x == p[x].parent)
		return x;
	temp = p[x].parent;
	p[x].parent = find(temp);
	p[x].relation = (p[x].relation + p[temp].relation) % 2;
	return p[x].parent;
}

int main()
{
	//freopen("Input.txt", "r", stdin);
	int ncase;
	int num, info;
	char ope;
	int a, b;
	int root1, root2;
	scanf("%d", &ncase);
	while(ncase--)
	{
		scanf("%d%d", &num, &info);
		for(int i = 1; i <= num; ++i)
		{
			p[i].parent = i;
			p[i].relation = 0;
		}
		for(int i = 0; i < info; ++i)
		{
			scanf("%*c%c %d%d", &ope, &a, &b);
			root1 = find(a);
			root2 = find(b);
			if(ope == 'D')
			{	
				if(root1 != root2)
				{
					p[root2].parent = root1;
					p[root2].relation = (p[a].relation + 1 + 2 - p[b].relation) % 2;
				}
			}
			else
			{
				if(num == 2 && ope == 'A' && a != b) //2个人时候肯定不同团伙
					printf("In different gangs.\n");
				if(root1 != root2)
					printf("Not sure yet.\n");
				else
				{
					if((2 - p[a].relation + p[b].relation) % 2 == 1)
						printf("In different gangs.\n");
					else
						printf("In the same gang.\n");
				}
			}
		}
	}
	return 0;
}