POJ 1703

比食物链那道题还要简单，简单的带权并查集应用，不过要注意只有两个人的特殊情况。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const char ansN[]= "Not sure yet.";
const char ansS[]= "In the same gang.";
const char ansD[]= "In different gangs.";
const int maxn= 1e5+5;
const int maxm= 1e5+5;

int fa[maxn], rk[maxn], tp[maxn]; // 0: same as fa 1: diff

int Find(int x)
{
	if (x== fa[x]){
		return fa[x];
	}

	int t= fa[x];
	fa[x]= Find(t);

	tp[x]= (tp[x]+tp[t])%2;

	return fa[x];
}
void Init(int n)
{
	memset(tp, 0, sizeof(fa));
	memset(rk, 0, sizeof(rk));

	for (int i= 1; i<= n; ++i){
		fa[i]= i;
	}
}
void Union(int a, int b)
{
	int pa= Find(a);
	int pb= Find(b);

	if (pa== pb){
		return;
	}

	if (rk[pa]> rk[pb]){
		fa[pb]= pa;
		++rk[pa];
		tp[pb]= (tp[b]+tp[a]+1)%2;
	}
	else{
		fa[pa]= pb;
		++rk[pb];
		tp[pa]= (tp[a]+tp[b]+1)%2;
	}
}

int main()
{
	int t, n, m, a, b;
	char op;
	scanf("%d", &t);

	while(t--){
		scanf("%d %d", &n, &m);
		Init(n);

		while(m--){
			scanf(" %c %d %d", &op, &a, &b);
			if ('D'== op){
				Union(a, b);
			}
			else{
				int pa= Find(a);
				int pb= Find(b);

				if (pa!= pb){
					if (2== n){
						puts("In different gangs.");
					}
					else{
						puts("Not sure yet.");
					}
					continue;
				}
				if (tp[a]== tp[b]){
					puts("In the same gang.");
				}
				else{
					puts("In different gangs.");
				}
			}
		}
	}

	return 0;
}