题意：有N名来自两个帮派的坏蛋，已知一些坏蛋两两不属于同一帮派，求判断给定两个坏蛋是否属于同一帮派。
思路：
解法一: 编号划分
定义并查集为：并查集里的元素i-x表示i属于帮派x，同一个并查集的元素同时成立
可见所有元素个数为2 * N，如果i表示属于帮派A，那么i + N表示属于帮派B，每次输入两个人不在同一帮派的时候，就合并他们分属两个帮派的元素。
#include <iostream>
using namespace std;
#define MAX_N 100000 * 2 + 16
int parent[MAX_N];
int height[MAX_N];
void init(const int& n)
{
for (int i = 0; i < n; ++i)
{
parent[i] = i;
height[i] = 0;
}
}
int find(const int& x)
{
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int x, int y)
{
x = find(x);
y = find(y);
if (x == y)return;
if (height[x] < height[y])
parent[x] = y;
else
{
parent[y] = x;
if (height[x] == height[y])
++height[x];
}
}
bool same(const int& x, const int& y)
{
return find(x) == find(y);
}
int main()
{
int T;
cin >> T;
while (T--)
{
int N, M;
cin >> N >> M;
init(N * 2);
char message;
int x, y;
getchar();
while (M--)
{
scanf("%c%d%d", &message, &x, &y);
getchar();
if (message == 'A')
{
if (same(x, y))
{
cout << "In the same gang." << endl;
}
else if (same(x, y + N))
{
cout << "In different gangs." << endl;
}
else
{
cout << "Not sure yet." << endl;
}
}
else
{
unite(x, y + N);
unite(x + N, y);
}
}
}
return 0;
}
解法二：
已知A与B不在一组，B与C不在一组，因为就两组，可得A与C一组。
r[] = 0 表示其根节点属于同一个帮派； r[] = 1表示与其根节点属于不同的帮派。
分析：
开始时初始化自己是自己的父亲 p[x] = x，自己与自己属于同一类 r[x] = 0.
一旦输入 D 断定 x 和 y 属于不同集合后，就连接 x 和 y 所在的树，同时更新 r[]
如果 find(x) 不等于 find(y) 说明还没有判断过 x 与 y 直接输出关系不确定即可
如果 find(x) 等于 find(y)，但是他们的r不等，说明属于不同帮派，输出In different gangs.
如果他们的r相等，说明属于同一个帮派，则输出In the same gang
注意：
1.find()函数寻找根节点的时候要不断的更新 r
根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系
如果 a 和 b 的关系是 r1, b 和 c 的关系是 r2,
那么 a 和 c 的关系就是(r1 + r2) % 2 //因为只用两种情况所以对 2 取模。
2.Union()联合两棵树的时候也要更新两棵树的根的关系
定义：fx 为 x的根节点， fy 为 y 的根节点
联合时，使得 p[fx] = fy; 同时也要寻找 fx 与 fy 的关系。关系为：（r[x] + r[y] + 1）% 2
#include<cstdio>
const int maxn = 100000 + 10;
int p[maxn]; //存父亲节点
int r[maxn]; //存与根节点的关系，0 代表同类， 1代表不同类
int find(int x) //找根节点
{
if (x == p[x]) return x;
int t = p[x]; //记录父亲节点 方便下面更新r[]
p[x] = find(p[x]);
r[x] = (r[x] + r[t]) % 2; //根据子节点与父亲节点的关系和父节点与爷爷节点的关系，推导子节点与爷爷节点的关系
return p[x];
}
void Union(int x, int y)
{
int fx = find(x);
int fy = find(y);
p[fx] = fy;
r[fx] = (r[x] + 1 + r[y]) % 2; //fx与x关系 + x与y的关系 + y与fy的关系 = fx与fy的关系
}
void set(int n)
{
for (int x = 1; x <= n; x++)
{
p[x] = x; //自己是自己的父节点
r[x] = 0; //自己和自己属于同一类
}
}
int main()
{
int T;
int n, m;
scanf("%d", &T);
while (T--)
{
scanf("%d%d%*c", &n, &m);
set(n);
char c;
int x, y;
while (m--)
{
scanf("%c%d%d%*c", &c, &x, &y); //注意输入
if (c == 'A')
{
if (find(x) == find(y)) //如果根节点相同，则表示能判断关系
{
if (r[x] != r[y]) printf("In different gangs.
");
else printf("In the same gang.
");
}
else printf("Not sure yet.
");
}
else if (c == 'D')
{
Union(x, y);
}
}
}
return 0;
}