在写程序解决问题中，通常会遇到集合类问题。例如集合的合并、查找、插入。并查集可以解决大多数集合类问题。
0x00、并查集的定义和存储
并查集实际上是一种树，一般使用静态数组的方式来定义比较方便。
#defind MAXN 50
int S[MAXN];接着我们初始化它
#include <algorithm>
fill(S, S + MAXN, -1);这里数组元素下标表示元素的“ID”或编号，数组存储的值表示这个元素的父节点的值。
例如两个集合：{1,2,3}，{4,5,6,7}，在并查集中表示为：
[-1, -1, 1, 1, -1, 4, 4, 4]
S[0]=-1是因为初始化，S[1]=S[4]=-1是因为将1和4看做根.每个集合只能有一个根，这个根在这个集合中是任意选取的。
S[2]=1表示2的父亲节点是1，S[3] = 1表示3的父节点也是1。当然，S[3]=2也没错，因为都是一个集合内的，但是一般我们不这么写。原因请继续阅读到【路径压缩】。
0x01、并查集的查找与合并
对于任何一个元素，一般用它的根节点表示他属于哪个集合。这就涉及到了并查集如何寻找根节点。根节点的特征是数组内的值为-1，所以我们只需要递归搜索，找到-1并将-1所在的下标返回即可。
int Find(int x, int *S){ //S为并查集，x为待查找的元素
if(x < 0) return x; //x为负数，说明x为根节点，直接返回
else return Find(S[x], S); //x不是根节点，就看看S的父亲节点S[x]是不是根节点
}这样就实现了查找操作。
对于合并操作，只需要将根节点合并在一起即可
void Union(int x1, int x2, int *S){ //注意函数名字不能是u(小写)nion（C语言关键字）
int root1 = Find(x1, S);
int root2 = Find(x2, S);
S[root1] = root2; //或者S[root2] = root1
}0x02、并查集的按秩归并
假想一种很糟糕的情况：如果并查集经过了大量插入后的数组为：[-1, -1, 1, 2, 3, 4, 5, ...., 99999]
2,3,4....99999这些数字的根节点都是1，但是这个并查集已经退化成一个链表的形式了，对并查集的Find操作就需要遍历整个数组，十分浪费时间。
为了解决这样的问题，最好的方法是按秩归并。
按秩归并一般是比较树的规模，将元素个数少的集合归并到元素多的集合中。存放元素个数，仍然用上面 的方法，使用负数存放到根节点中。
修改Union的代码：
void Union(int x1, int x2, int *S){
int root1 = Find(x1, S);
int root2 = Find(x2, S);
if( (-S[root2]) > (-S[root1]) ){ //集合1元素个数小于集合2元素个数
S[root2] += S[root1]; //计算合并后元素个数
S[root1] = root2; //合并
}else{
S[root1] += S[root2]; //计算合并后元素个数
S[root2] = root1; //合并
}
}有种类型的题目，可能要求求并查集集合中元素的个数，使用第二种方案可以直接通过根节点存放的数据的负数来计算集合中有多少元素。
0x03、并查集的路径压缩
路径压缩的原理其实用一个图就能很好的解释（画的不好，凑合着看...）
上面的是按照顺序插入的并查集，根节点为1，并查集数组(省略掉0，从1开始)为[-1, 1, 2, 3, 4, 5]
下面的是路径压缩后的并查集，数组为[-1, 1, 1, 1, 1, 1]
显然，在一次Find操作中，上面的路径需要遍历5次才能到root，下面只需要遍历一次即可，这样会节省很多时间。
路径压缩我们直接在find函数中进行：
int Find(int x, int *S){
if(S[x] < 0) //说明已经是根节点了
return x;
else //不是根节点，递归查找
return S[x] = Find(S[x], S); //查找的同时，将路径上的所有父亲节点赋值为根节点，进行压缩路径
}