引言
并查集(Union-Find Set)，顾名思义，是实现快速合并集合与查询元素所在集合的数据结构。
它在包括但不限于最小生成树Kruskal算法的众多算法中有很好的使用效果。
结构
形象地看，并查集是一个类似于森林的结构，同一个集合的元素都连在同一棵树上，查询操作即寻找树的根节点（唯一编码），合并操作即将一个集合的根连在另一棵树上。
抽象地看，这是一个记录父节点的数组（优化算法还包括这个集合的元素数量）。
性质
- 该数组记录父节点编号。
- 每个集合的根节点是一个具有特殊标记（一般其父节点指向其本身）的点。
操作
- 查询元素所在集合
根据性质，只需要依照沿着这个集合的树向上爬即可。 - 合并两个元素所在的集合
根据操作1找到两个根节点后连接即可。
代码实现
基础版
//////////////////////////////////////////////////////////////////////
//Target: To implement the Union-Find Set
//@Author: Pisceskkk
//Date: 2019-2-24
//////////////////////////////////////////////////////////////////////
#define Max_N (int)1e6
int n,f[Max_N];
void init(int n){
for(int i=1;i<=n;i++){
f[i] = i;
}
}
int find(int x){
return (f[x) == x)?x:find(f[x]);
}
bool mege(int x,int y){
x = find(x);
y = find(y);
if(x == y) return 0;
f[x] = y;
return 1;
}
优化
路径压缩
问题来了：在特殊情况下，这棵树可能是一条长长的链。设链的最后一个结点为x，则
每次执行find(x)都会遍历整条链，效率十分低下。看上去是个很棘手的问题，其实改进方法
很简单。既然每棵树表示的只是一个集合，因此树的形态是无关紧要的，并不需要在“查
找”操作之后保持树的形态不变，只要顺便把遍历过的结点都改成树根的子结点，下次查找
就会快很多了。
——《算法竞赛入门经典》刘汝佳
正如刘犇所言，我们可以通过路径压缩来解决这一个特殊情况。
int find(int x){
return f[x] = (f[x] == x ? x : find(f[x]));
}
另一个版本是非递归版。虽然个人认为，在添加路径压缩之后，这个递归版函数应该不会出现递归层数过深而导致爆栈的情况。
int find(int x){
int fx = f[x];
while(fx != f[fx]){
fx = f[fx];
}
while(x != fx){
int temp = f[x];
f[x] = fx;
x = temp;
}
return fx;
}
启发式合并
路径压缩虽然好处多多，但是也有一个显而易见的缺陷——丢失大量信息，尤其是在一些要求解连接时间的题目（e.g. BZOJ 4668 - 冷战 ）中，路径压缩就不再是最好的优化方法了。
那么我们要如何才能有效解决上述问题，同时又不致丢失数据呢？
思考这样一个问题，查找操作的时间复杂度取决于什么？
那当然是树的高度啦。那么我们降低复杂度的方法就是让树高尽量小。
考虑两棵树合并，一颗树高为6，另一棵为2，那么合并之后树高可能为几？7或者6。那么合并方案也就出现了，往树高大的树上合并，这也就是启发式合并。
#define Max_N (int)1e6
int n,f[Max_N],height[N];
void init(int n){
for(int i=1;i<=n;i++){
f[i] = i;
height[i] = 1;
}
}
int find(int x){
while(f[x] != x)x=f[x];
return x;
}
bool mege(int x,int y){
x = find(x);
y = find(y);
if(x == y) return 0;
if(height[x] > height[y]){
f[y] = x;
}
else if(height[x] < height[y]){
f[x] = y;
}
else {
f[y] = x;
height[x]++;
}
return 1;
}
除了以高度为标准进行启发式合并，刘犇还提到了一个按秩合并的方法（个人感觉这是一个和高度差不太多的量）。
一个优化是：把小的树合并到大树中，这样会让深度不太大。这个优化称为启发式合并。(rank[i]) 表示 (i) 的秩，并用秩来代替深度做刚才提到的启发式合并。
技巧
标记
既然数组(f[i])只负责标记，那么我们也就不必局限于f[i] == i这一种标记。
- 初始化0
简单的memset(f,0,sizeof(f))也是可以满足需求的。 - 与height(或 rank)数组合并
将(f[i])数组设为负数，其绝对值等于树高或者树的秩也是个不错的选择。
非路径压缩
当没有路径压缩时，可以通过删除最后一次合并来达到集合拆分的操作。
代码实现暂略。
如果还有其他技巧将会及时更新。