扩展域并查集
普通的并查集只能解决各元素之间仅存在一种相互关系。例如在普通并查集的《亲戚》问题中，a 和 b 是亲戚，b 和 c 是亲戚，则 a 和 c 也是亲戚。
但如果存在各元素之间存在多种相互关系，普通并查集就无法解决。比如：a 和 b 是敌人，b 和 c 是敌人，那么 a 和 c 的关系是什么呢？根据'敌人的敌人是朋友'，a 和 c 其实是朋友关系。
解决这类有多种关系的问题需要对并查集进行扩展：将每个元素拆分成多个域，每个域代表一种状态或者关系。通过维护这些域之间的关系，来处理复杂的约束条件。
比如现在有 n 个人，它们之间可能是朋友关系也可能是敌人关系。我们可以把数组扩大成两倍，开辟一个大小为 2n 的数组，[1, n] 这个区间表示朋友域，[n+1, 2n] 区间表示敌人域。接下来：
- 如果 x 和 y 是朋友，正常处理，把 x 和 y 合并成一个集合；
- 如果 x 和 y 是敌人，那么我们把 x 和 y+n 合并成一个集合，表示 x 和 y 是敌人，同时也把 x+n 和 y 合并成一个集合。
这样就可以利用两个域，将两种关系维护起来。
实战案例
1. 团伙
【题目链接】
【题目描述】
现在有 n 个人，他们之间有两种关系：朋友和敌人。我们知道：一个人的朋友的朋友是朋友，一个人的敌人的敌人是朋友。
现在要对这些人进行组团。两个人在一个团体内当且仅当这两个人是朋友。请求出这些人中最多可能有的团体数。
【输入格式】
第一行输入一个整数 n 代表人数。
第二行输入一个整数 m 表示接下来要列出 m 个关系。
接下来 m 行，每行一个字符 opt 和两个整数 p, q，分别代表关系（朋友或敌人），有关系的两个人之中的第一个人和第二个人。其中 opt 有两种可能：如果 opt 为
F，则表明 p 和 q 是朋友。如果 opt 为E，则表明 p 和 q 是敌人。
【输出格式】
一行一个整数代表最多的团体数。
【说明/提示】
对于 100% 的数据，2 ≤ n ≤ 1000，1 ≤ m ≤ 5000，1 ≤ p, q ≤ n。
解题思路
开辟一个 2n+10 大小的数组，[1, n] 区间表示朋友域，[n+1, 2n] 区间表示敌人域。如果 x 和 y 是朋友，那么把 x 和 y 合并成一个集合；如果 x 和 y 是敌人，那么我们把 x 和 y+n 合并成一个集合，x+n 和 y 合并成一个集合。
处理完之后我们只需看有多少个根节点即可。
代码实现
#include <iostream>
using namespace std;
const int N = 1010;
int pa[2 * N]; // 扩展域并查集，两种关系，扩展出两个域
int n, m;
{
( i = ; i <= * n; i++) pa[i] = i;
}
{
(pa[x] == x) x;
pa[x] = (pa[x]);
}
{
fx = (x);
fy = (y);
pa[fx] = fy;
}
{
cin >> n >> m;
();
(m--) {
opt;
cin >> opt;
p, q;
cin >> p >> q;
(opt == ) (p, q);
{
(p + n, q);
(q + n, p);
}
}
cnt = ;
( i = ; i <= n; i++) {
(pa[i] == i) cnt++;
}
cout << cnt << endl;
;
}
