题目链接：http://poj.org/problem?id=1703
题意：两个坏蛋属于不同的组织，给出两个坏蛋判定是否一个组织。
题解：已知每次输入的两个帮派人员 x, y; 合并 (x, y + N), (x + N, y)。判定时，如果 (x, y) 属于同一个 根，就是同一个组织，(x, y+N) 属于同一个根，则说明是不同组织。不确定则无解。
#include <iostream>
using namespace std; const int maxn = * + ;
int Rank[maxn], par[maxn];
void solve(); void init(const int& n) {
for (int i = ; i < n; i++) {
par[i] = i;
Rank[i] = ;
}
} int find(const int& x) {
if (par[x] == x) {
return x;
}
else {
return par[x] = find(par[x]);
}
} void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y) return ; if (Rank[x] < Rank[y]) {
par[x] = y;
}
else {
par[y] = x;
if (Rank[x] == Rank[y]) {
++Rank[x];
}
}
} bool same(int x , int y)
{
return find(x) == find(y);
} void solve()
{
int T, N, M;
int x, y; char cmd;
scanf("%d", &T); while (T--)
{
scanf("%d%d", &N, &M);
init(N * ); getchar(); while (M--)
{
//忽略每次输入后的回车符
scanf("%c%d%d%*c", &cmd, &x, &y);
//检查
if (cmd == 'A') {
if (same(x, y)) {
printf("In the same gang.\n");
}
else if (same(x, y + N)) {
printf("In different gangs.\n");
}
else {
printf("Not sure yet.\n");
}
}
else {
//合并 (x, y+N) 或 (x+N, y)
unite(x, y + N);
unite(x + N, y);
}
} } } int main()
{
solve();
return ;
}