POJ 1703 Find them, Catch them 并查集

题意：给你t组数据，每组数据给你编号为1-n的坏人，这些坏人要么属于团伙A，要么属于团伙B，然后给你m次操作：

　　　A操作：询问x和y是不是同一个团伙

　　　D操作：告诉你x和y不是同一个团伙

思路：和POJ 1182 食物链是一样的。http://www.cnblogs.com/sevenun/p/5474343.html

AC代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_N = 200005;
int t,n,m,fa[MAX_N],x,y;
char op[2];
int find(int x)
{
	if(x == fa[x]) return x;
	else return fa[x] = find(fa[x]);
}
void unite(int x, int y)
{
	x = find(x);
	y = find(y);
	if(x == y) return;
	fa[x] = y;
}
bool same(int x, int y)
{
	return find(x) == find(y);
}
void init()
{
	for(int i = 1; i <= n*2; i++)
		fa[i] = i, opp[i] = 0;
}
void solve()
{
	while(m--)
	{
		scanf("%s %d %d", op, &x, &y);
		if(op[0] == 'A')
		{
			if(same(x,y))
				puts("In the same gang.");
			else if(same(x,y+n))
				puts("In different gangs.");
			else puts("Not sure yet.");
		}else
		{
			unite(x,y+n);
			unite(x+n,y);
		}
	}
}
int main()
{
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d %d", &n, &m);
		init();
		solve();
	}
	return 0;
}