并查集(Union-Find Set，个人常写作UnionSet)，就是可以合并，可以查询的集合。朴素并查集是最简单的数据结构之一。
给定n个元素，最初每个元素在一个集合中，要求实现两种操作：
- 合并两个元素所在集合
- 查询两个元素是否在同一集合
我们可以把每个集合进行标号，如果两个元素所在集合标号一样，说明在同一个集合里。
考虑合并操作，如果暴力将其中一个集合中所有元素标号改成另一个，复杂度爆炸。所以我们使用树形结构来维护。如果将两个集合合并，就将两个集合之间连边。查询时找树根即可。
void init() {
for(int i = 1; i <= num; ++i) {
father[i] = i;//最初所有元素标号都为自己
}
}
int find(int son) {//找树根
while(father[son] != son) son = father[son];
return son;
}
void join(int a, int b) {//合并
father[find(a)] = find(b);//合并树根
return;
}
有些人会不进行这样的init，然后判断fa是否为0，也是一种方法。
但是只是这样的话，构造数据是可以将复杂度卡到爆炸的，所以便出现了各种优化：
按秩合并(单次操作复杂度可看作 $\rm O(logn)$ )
考虑两个集合所在的树的高度depth[a]和depth[b]，我们可以将高度小的树根接在高度大的树根上，能比随便接在查询时快一些。
void join(int a, int b) {
a = find(a);
b = find(b);
if(depth[a] > depth[b]) std::swap(a, b);
father[a] = b;
if(depth[a] == depth[b]) ++depth[b];//只用根记录depth即可
return;
}
按秩合有时会用到，但并不是重点，不会也可以，所以也不重点讲解。重点在路径压缩。
路径压缩(单次操作复杂度极低，可看作 $\rm O(1)$ )
考虑到一个集合的树只要连通，长成什么样子都是可以的，所以我们可以在find时把一路的father都直接改到根上，以后再查询的时候就能少走不少路。这样，按秩合并也可以舍弃了。
路径压缩并查集的复杂度为 $\rm O(\alpha(n))$ ，其中 $\alpha$ 是 $Ackermann$ 函数的反函数。这个复杂度可近似看作 $\rm O(1)$ 。
//传说中的一行一个并查集
int find(int son) {
return father[son] == son ? son : father[son] = find(father[son]);
}
void join(int a, int b) {
father[find(a)] = find(b);
return;
}
模板：洛谷P3367
代码：
#include<cstdio>
class UnionSet {
private:
int *father;
public:
UnionSet() : father(NULL) { }
UnionSet(int len) : father(NULL) {
init(len);
}
void init(int len) {
delete[] father;
father = new int[len + 1];
for(int i = 0; i <= len; ++i) {
father[i] = i;
}
}
int find(int son) {
return son == father[son] ? son : father[son] = find(father[son]);
}
void join(int a, int b) {
father[find(a)] = find(b);
}
};
int main() {
int num;
int open;
scanf("%d%d", &num, &open);
UnionSet set(num);
for(int i = 1; i <= open; ++i) {
int ope;
int a, b;
scanf("%d%d%d", &ope, &a, &b);
if(ope == 1) {
set.join(a, b);
} else {
puts(set.find(a) == set.find(b) ? "Y" : "N");
}
}
return 0;
}
接下来讲几个并查集的扩展：
联合并查集
又叫关系并查集。正常并查集是维护两个元素在同一集合中，而联合并查集则是将所有元素分为两个（有些题可以更多）部分，所有元素非此即彼。
举个例子：
n个罪犯，2个监狱。有些对罪犯如果关在同一个监狱会产生 $c_i$ 的影响。问最优分配下最小的最大影响。
显然应该贪心从大到小处理，使产生影响的两个罪犯不在同一监狱里。当两个罪犯必须在一个监狱里时，输出影响值即可。
如何处理“两个罪犯不在同一监狱里”？
考虑对于每个人，建立两个并查集中的结点，一个表示自己所在监狱，一个代表自己不在的监狱。当两个罪犯 $A,B$ 不能在同一监狱时，合并 $A$ 在的监狱与 $B$ 不在的监狱，再合并 $B$ 在的监狱与 $A$ 不在的监狱即可。
代码：
#include<cstdio>
#include<algorithm>
class UnionSet {
private:
int *father;
public:
UnionSet() : father(NULL) { }
UnionSet(int len) : father(NULL) {
init(len);
}
void init(int len) {
delete[] father;
father = new int[len + 1];
for(int i = 0; i <= len; ++i) {
father[i] = i;
}
}
int find(int son) {
return son == father[son] ? son : father[son] = find(father[son]);
}
void join(int a, int b) {
father[find(a)] = find(b);
}
};
int a[100005];
int b[100005];
int cost[100005];
int id[100005];
int main() {
int num;
int pairn;
scanf("%d%d", &num, &pairn);
UnionSet set(num << 1);
for(int i = 1; i <= pairn; ++i) {
scanf("%d%d%d", a + i, b + i, cost + i);
id[i] = i;
}
std::sort(id + 1, id + 1 + pairn, [](int a, int b) {
return cost[a] > cost[b];
});//c++11
for(int i = 1; i <= pairn; ++i) {
if(set.find(a[id[i]]) == set.find(b[id[i]])) {
printf("%d\n", cost[id[i]]);
return 0;
}
set.join(a[id[i]], b[id[i]] + num);
set.join(a[id[i]] + num, b[id[i]]);
}
putchar('0');
return 0;
}
类似的题目还有：[NOI2001]食物链
权值并查集
又叫带权并查集。在并查集过程中维护每个节点与根节点的信息，在路径压缩和合并时更新。
$30000$ 个人，每次操作使 $i$ 所在列整体接到 $j$ 所在列后面，或者询问 $i$ 与 $j$ 的距离，不在同一列输出 $-1$ 。
splay傻逼题
用权值并查集就可以做了
详情参见代码。
#include<cstdio>
#include<cmath>
class UnionSet {
private:
int *father;//根节点
int *size;//所在一列的大小
public:
int *dis;//到队头的距离
UnionSet() : father(NULL), size(NULL), dis(NULL) { }
UnionSet(int len) : father(NULL) {
init(len);
}
void init(int len) {
delete[] father;
delete[] size;
delete[] dis;
father = new int[len + 1];
size = new int[len + 1];
dis = new int[len + 1];
for(int i = 0; i <= len; ++i) {
father[i] = i;
dis[i] = 0;
size[i] = 1;
}
}
int find(int son) {
if(father[father[son]] != father[son]) {//注意不要修改过度
int fa = father[son];//记录原父亲方便修改
father[son] = find(father[son]);//放在修改之前，优先修改父亲
dis[son] += dis[fa];//dis加上fa的dis
size[son] = size[father[son]];
}
return father[son];
}
void join(int a, int b) {
//join顺序很重要，一定要把a连在b下面
a = find(a);
b = find(b);//顺便更新了b的信息
father[a] = b;
dis[a] += size[b];//排在队尾，长度增加
size[b] += size[a];//b的大小增加了
size[a] = size[b];//a的大小与b相同
father[find(a)] = find(b);
}
};
UnionSet set(30000);
int main() {
int ope;
scanf("%d", &ope);
int a, b;
for(int i = 1; i <= ope; ++i) {
char ch = ' ';
while(ch != 'C' && ch != 'M') {
ch = getchar();
}
if(ch == 'M') {
scanf("%d%d", &a, &b);
set.join(a, b);//注意合并顺序
} else {
scanf("%d%d", &a, &b);
if(set.find(a) == set.find(b)) {
printf("%d\n", std::abs(set.dis[a] - set.dis[b]) - 1);
} else {
puts("-1");
}
}
}
return 0;
}
以上两个是并查集的两个基础变化。我们再来讨论一下稍微高级一点的。
回滚并查集
即带撤销并查集，不是可持久化并查集。
要求实现并查集的基本操作，并且新增撤销操作，撤销上一次join。
回滚并查集必须要按秩合并来实现。思路大概是用栈来维护每次修改的位置与修改前的内容，撤销时覆盖回去就好了，不难实现。
class UnionSet {
private:
int *father;
int *depth;
std::stack<std::pair<int, int> > fatherc;
std::stack<std::pair<int, int> > depthc;
public:
UnionSet() : father(NULL) { }
UnionSet(int len) : father(NULL) {
init(len);
}
void init(int len) {
delete[] father;
father = new int[len + 1];
delete[] depth;
depth = new int[len + 1];
while(!fatherc.empty()) fatherc.pop();
while(!depthc.empty()) depthc.pop();
for(int i = 0; i <= len; ++i) {
father[i] = i;
depth[i] = 0;
}
}
int find(int son) {
while(father[son] != son) son = father[son];
return son;
}
void join(int a, int b) {
a = find(a);
b = find(b);
if(depth[a] > depth[b]) std::swap(a, b);
fatherc.push(std::make_pair(a, father[a]));
father[a] = b;
depthc.push(std::make_pair(b, depth[b]));//为了写起来方便，即使depth没被修改也记录一下
if(depth[a] == depth[b]) ++depth[b];
return;
}
void undo() {
father[fatherc.top().first] = fatherc.top().second;
fatherc.pop();
depth[depthc.top().first] = depthc.top().second;
depthc.pop();
}
};
可持久化并查集
就是用主席树实现按秩合并并查集，复杂度 $mlog^2n$ ，没什么好说的。
前置技能：主席树。
代码：暂时犯懒不想写了，TODO吧。