一、前言
作为家喻户晓的并查集，运用简单的几行代码就实现了多个数据间从属关系的高效维护和查找。最基本的并查集没啥好说的了，定义一个fa数组表示x的父亲，初始化所有数据一开始的父亲是自己，然后就是查找和合并的操作，自认为最简单的模板见下：
int fa[x];
int f(int x) {return fa[x] == x ? x : fa[x] = f(fa[x]);}//查找x的父亲顺带维护缩短路径
int main() {
for(int i = 1; i <= N; i++) fa[i] = i;//初始化，别忘
int x = f(x), y = f(y);
if(x!=y) fa[x] = y;//合并
}
下面要讲的是和并查集有关的两个拓展应用：带边权的并查集和拓展域。
二、带边权的并查集
并查集的本质其实就是一个森林，维护的是每个子节点和根节点的关系，带边权的并查集顾名思义就是在原并查集的基础上再维护了一个权值，下面以两道例题加以理解。
AcWing 239. 奇偶游戏
题面
小A和小B在玩一个游戏。
首先，小A写了一个由0和1组成的序列S，长度为N。
然后，小B向小A提出了M个问题。
在每个问题中，小B指定两个数 l 和 r，小A回答 S[l~r] 中有奇数个1还是偶数个1。
机智的小B发现小A有可能在撒谎。
例如，小A曾经回答过 S[1-3] 中有奇数个1， S[4-6] 中有偶数个1，现在又回答 S[1~6] 中有偶数个1，显然这是自相矛盾的。
请你帮助小B检查这M个答案，并指出在至少多少个回答之后可以确定小A一定在撒谎。
即求出一个最小的k，使得01序列S满足第1-k个回答，但不满足第1-k+1个回答。
输入格式
第一行包含一个整数N，表示01序列长度。
第二行包含一个整数M，表示问题数量。
接下来M行，每行包含一组问答：两个整数l和r，以及回答“even”或“odd”，用以描述S[l-r] 中有偶数个1还是奇数个1。
输出格式
输出一个整数k，表示01序列满足第1-k个回答，但不满足第1-k+1个回答，如果01序列满足所有回答，则输出问题总数量。
数据范围
$N≤10^9,M≤10000$
输入样例：
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
输出样例：
3
分析
首先用前缀和思想，s[i]表示前i个序列中1的个数的奇偶性，那么题目每次给出L-R中1的个数的奇偶性，实际上就是告诉你s[R] – s[L-1]的奇偶性，若为奇则s[R]和s[L-1]奇偶性不同，否则相同。所以此题就转化为这样一个问题：每次告诉你两个数L，R，并告诉你L-1和R同类还是异类（odd表示不同类，even表示同类），让你判断是否矛盾。
那么就可以用到并查集来做，边权表示每个节点和father的关系（同类还是异类，用0和1表示，同数组d存储）。下面记L-1为x，R为y，继续推导（以x和y同类为例，即even）：
– 如果x和y已经属于一个集合则无需合并，若d[x]和d[y]不同（即dx^dy=1），则表示两者其中一个与父节点同类，另外一个与父节点不同类，而两者的父亲相同，则两者不同类，这和“x和y同类”前提矛盾，若dx^dy=0则无矛盾。
– 若两者不属于同一集合，则需要进行合并操作，我们假设将x合并到y的集合中，主要是d数组如何维护？首先我们要保证合并的合法性，即合并后x和y依旧同类，设px为x父节点，py为y父节点，则父节点的合并就是fa[px] = py;,设d[px] = ？，即合并后px到py的权值为？，那么可以得到：dx^?就是x到py的权值，由于同类用0表示，则dx^?^dy = 0，可得? = dx^dy,即d[px] = dx^dy。
若x和y异类其实类似，不进行推导，结论见下图（y总帅！）：
另外，此题数据量不大但是数据范围大，需要进行离散化，用unordered_map在线处理即可。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
unordered_map<int, int> mp;
int n, m;
int fa[maxn], d[maxn];
int get_id(int x) {//离散化
if (mp.count(x) == 0) mp[x] = ++n;
return mp[x];
}
int f(int x) {
if (x != fa[x]) {
int root = f(fa[x]);
d[x] ^= d[fa[x]];
fa[x] = root;
}
return fa[x];//不能写x，递归返回时第一层x==fa[x]，但是第二层的时候x!=fa[x]
}
int main(int argc, char const *argv[]) {
cin >> n >> m;
for (int i = 1; i <= maxn; i++) fa[i] = i;
int res = m;
n = 0;
for (int i = 1; i <= m; i++) {
int x, y;
string s;
cin >> x >> y >> s;
x = get_id(x - 1), y = get_id(y);
int pa = f(x), pb = f(y);
int t = 0;
if (s == "odd") t = 1;
if (pa == pb) {
if (d[x] ^ d[y] != t) {
res = i - 1;
break;
}
} else {
fa[pa] = pb;
d[pa] = d[x] ^ d[y] ^ t;
}
}
cout << res << endl;
return 0;
}
AcWing 238. 银河英雄传说
题面
有一个划分为N列的星际战场，各列依次编号为1,2,…,N。
有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。
有T条指令，每条指令格式为以下两种之一：
1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。
2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
现在需要你编写一个程序，处理一系列的指令。
输入格式
第一行包含整数T，表示共有T条指令。
接下来T行，每行一个指令，指令有两种形式：M i j或C i j。
其中M和C为大写字母表示指令类型，i和j为整数，表示指令涉及的战舰编号。
输出格式
你的程序应当依次对输入的每一条指令进行分析和处理：
如果是M i j形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是C i j形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目，如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。
数据范围
$N≤30000,T≤500000$
输入样例：
4
M 2 3
C 1 2
M 2 4
C 4 2
输出样例：
-1
1
分析
每次M指令就是一次并查集的合并操作，由于C查询的是两者之间的战舰个数，用边权数组d[x]表示节点x前到父节点间有几艘战舰，则x和y之间间隔战舰数为：max(abs(dx-dy)-1,0)。另外就是如何在合并的时候维护d数组，需要一个siz数组表示某个节点下面有几艘战舰，具体画个图结合代码就可以明白了。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 3e4 + 10;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
int fa[maxn], d[maxn], siz[maxn];//siz记录当前点下面有几个战舰,d记录当前点到最高父亲间有几个战舰
int f(int x) {
if (fa[x] != x) {
int root = f(fa[x]);
d[x] += d[fa[x]];
fa[x] = root;
}
return fa[x];
}
int main(int argc, char const *argv[]) {
int t;
cin >> t;
for (int i = 0; i <= maxn; i++) fa[i] = i, siz[i] = 1;
while (t--) {
char op[4];
int x, y;
scanf("%s %d %d", op, &x, &y);
int x1 = f(x), y1 = f(y);
if (op[0] == 'M') {
d[x1] = siz[y1];//x1接到y下面，则x1前面的战舰个数就是y1下方的战舰个数
siz[y1] += siz[x1];//x1接到y1下面了，那么多了x1下方所有的战舰
fa[x1] = y1;
} else {
if (x1 != y1)
puts("-1");
else {
printf("%d\n", max(0, abs(d[x] - d[y]) - 1));
}
}
}
return 0;
}
三、拓展域
一个比较巧妙的思想，运用枚举的思想，考虑全部的可能情况，下面以AcWing 239. 奇偶游戏（见上方）为例讲解。
分析
还是用x代表L-1，y代表R,x和y都有两种状态：奇和偶，用x代表x为奇数的情况，x+n代表x为偶数的情况，y表示y为奇数的情况，y+n表示y为偶数的情况。
分两种情况考虑：
- x和y同类，只有两种可能：x和y都为奇数，或者x和y都为偶数，故合并x，y以及x+n，y+n，表示这些属于一个集合。合并前要判断，x和y+n是否属于一个集合，如果属于一个集合说明x和y是异类，矛盾了。
- x和y异类，也是两种可能：x为奇，y为偶，或者x为偶y为奇，故合并x，y+n以及x+n，y，表示这些属于一个集合。合并前要判断，x和y是否属于一个集合，如果属于一个集合说明x和y是同类，矛盾了。
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e4 + 10, Base = maxn / 2;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
unordered_map<int, int> mp;
int n, m;
int p[maxn];
int get_id(int x) {
if (mp.count(x) == 0) mp[x] = ++n;
return mp[x];
}
int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
int main(int argc, char const *argv[]) {
cin >> n >> m;
for (int i = 1; i <= maxn; i++) p[i] = i;
int res = m;
n = 0;
for (int i = 1; i <= m; i++) {
int a, b;
string type;
cin >> a >> b >> type;
a = get_id(a - 1), b = get_id(b);
if (type == "even") {
if (find(a + Base) == find(b)) {
res = i - 1;
break;
}
p[find(a)] = find(b);
p[find(a + Base)] = find(b + Base);
} else {
if (find(a) == find(b)) {
res = i - 1;
break;
}
p[find(a + Base)] = find(b);
p[find(a)] = find(b + Base);
}
}
cout << res << endl;
return 0;
}
