并查集算法

　　并查集（union-find disjoint sets）是一种十分精巧和简洁的数据结构，主要用于处理不相交集合的合并问题。正如它的名字一样，并查集的主要的操作有合并（union）与查找（find）。一些算法也会用到并查集，比如求最小生成树的Kruskal算法。下面先通过举例说明并查集的基本概念。

并查集的引入

　　首先，我们怎么样来表示一个集合呢？其实很简单，只需要在这个集合里面随便找一个元素作为这个集合的代表就可以了。用哪个元素作为代表并不是我们关心的问题，我们关心的是，给定一个元素要找到它所属的那个集合。所谓找到所属的集合，也就是找到这个集合的代表元素。

　　比如我们现在有0，1，2，3，4，5，6，7这8个元素，他们各自所在的集合如下：

　　图中有3个集合，这3个集合的代表元素分别为1，6，5。其中代表元素为1的集合含有的元素有0，1，2，4；代表元素为6的集合含有元素有3，6，7；代表元素为5的集合含有的元素就只有5。

　　所以，如果我们要查找某一个元素属于哪一个集合，只需要从这个元素的节点开始，根据箭头方向一直向上找就可以了。当某个元素没有向外指出的箭头，就说明这个元素就是这个集合的代表元素。

　　比如，如果现在要找4是属于哪一个集合，根据上面的方法我们可以知道4这个元素在代表元素为1的这个集合中。如果要找5这个元素，那么5这个元素就在代表元素为5的集合中，同时代表元素为5的集合中就只有5这个元素。

　　现在我们要把代表元素为7的集合合并到代表元素为4的集合，我们需要先找到7所属的集合的代表元素6，以及4所属的集合的代表元素1，然后再让6指向1就完成了合并了。

　　上面大致讲解了查找和合并的实现过程，下面我们用代码来实现。先讲我常用的并查集算法。

　　先说明，集合用数组set来表示，数组的下标就是对应的元素，而数组存放的是该元素的上一个元素。就拿上面这个图来举例，我们的set数组是这样的：

　　set数组中存放的值有正数和负数。其中只有代表元素存放负数，这里的"-1"代表5是对应集合的代表元素，"-1"的绝对值也就是"1"说明在代表元素为5的这个集合中，含有元素的个数为1。同理，"-7"代表1是对应集合的代表元素，"-7"的绝对值也就是"7"说明在代表元素为1的这个集合中，含有元素的个数为7。而非代表元素存放正数，相应的值表示该元素的前一个元素（父节点或是索引）。

初始化

　　首先我们需要将每一个元素所属的集合初始化为其本身，也就是每一个元素所属集合的代表元素就是它自己，初始化为"-1"。

　　假如我们有n个元素，初始化的代码如下：

1 void initSet(int *set, int n) {
2     for (int i = 0; i < n; i++) {
3         set[i] = -1;
4     }
5 }

　　当然，你也可以简简单单的就一句话： std::fill(set, set + n, -1); ，达到同样的效果。

查找

　　与上面所说的方法一样，如果我们要找某一个元素所在的集合（的代表元素），就先找到它的前一个元素，如果没有前一个元素，那么它自己就是那个代表元素；如果有前一个元素，那么再找前一个元素的前一个元素，这样总是可以找到代表元素。

　　查找的代码如下：

1 int find(int *set, int x) {
2     while (x > 0) {
3         x = set[x];
4     }
5     return x;
6 }

合并

　　我们需要先找到要合并的那个元素所属集合的代表元素，然后才可以进行合并。

　　合并的代码如下：

1 void merge(int *set, int x, int y) {
2     int x = find(set, x);
3     int y = find(set, y);
4     set[y] = x;
5 }

　　这里我们始终把y所属的集合合并到x所属的集合。

路径压缩

　　考虑一种情况，如果有元素0，1，2，3，4。

　　上面合并后的结果就像一条链，随着链越来越长，每次我们从底部查找到根节点所需的时间也会越长。有没有什么方法可以减少链的长度，以提高查找的效率？当然有，那就是路径压缩。只需要在查询的过程中，把沿途的每个元素都指向代表元素就可以了，所以经过路径压缩后，上面的合并情况应该变成这个样子：

　　通过路径压缩改善后的查找代码也很简单，这里我们用递归的方法实现：

1 int find(int *set, int x) {
2     if (x < 0) return x;
3     else return set[x] = find(set, set[x]);
4 }

　　我们并不是直接返回集合的代表元素，而是先把集合的代表元素赋值给沿途的那个元素，让这个元素指向代表元素，然后再返回集合的代表元素。这样就实现了路径压缩。

按秩合并

　　这里我是按照集合的规模大小来进行合并的。

　　在上面的合并函数代码中，我们总是把后一个集合合并到前一个集合，也正是这种方法使得之前我们合并出一条很长的链。所以我们应该用一种更高效的方法来进行合并，避免合并出一条很长的链。

　　所以我们采用了按秩合并的方法，就是每次我们都是把规模小的集合合并到规模大的集合。而集合的规模，也就是元素的数量，可以通过代表元素在set数组中存放的值的绝对值知道。所以我们只需要找到合并元素所属集合的代表元素，然后比较两个集合元素个数大小，按照小并到大的规则来合并就可以了。

　　按秩合并（按规模大小）的代码如下：

 1 void merge(int *set, int x, int y) {
 2     int x = find(set, x);
 3     int y = find(set, y);
 4     if (set[x] > set[y]) {  // 注意我们比较的是负数，如果set[x] > set[y]，说明abs(set[x]) < abs(set[y])，也就是x所属的集合的规模小于y所属集合的规模 
 5         set[y] += set[x];   // 所以应该把x所属的集合合并到y所属的集合。先改变y集合的规模大小 
 6         set[x] = y;         // 再把x所属的集合合并到y所属的集合
 7     }
 8     else {                  //  y所属的集合的规模小于x所属集合的规模 
 9         set[x] += set[y];   // 所以应该把y所属的集合合并到x所属的集合。先改变x集合的规模大小
10         set[y] = x;         // 再把y所属的集合合并到x所属的集合 
11     }
12 }

并查集算法

　　下面给出改进后的并查集的完整代码（路径压缩与按秩合并）：

 1 void initSet(int *set, int n) {
 2     for (int i = 0; i < n; i++) {
 3         set[i] = -1;
 4     }
 5 }
 6
 7 int find(int *set, int x) {
 8     if (x < 0) return x;
 9     else return set[x] = find(set, set[x]);
10 }
11
12 void merge(int *set, int x, int y) {
13     int x = find(set, x);
14     int y = find(set, y);
15     if (set[x] > set[y]) {
16         set[y] += set[x];
17         set[x] = y;
18     }
19     else {
20         set[x] += set[y];
21         set[y] = x;
22     }
23 }

另外一种并查集算法

　　这种方法需要额外的一个rank数组，rank[n]，用来存放代表元素所属集合的秩（深度）。或者说，是存放每个根节点对应的树的深度（如果该元素不是根节点，其rank存放的值是以它作为根节点的子树的深度）。比如：

　　对应的按秩合并的规则是，把rand小的集合合并到rank大的集合。如果两个集合的秩大小相同，则让其中一个集合合并另外一个集合，同时把合并后的那个集合的rank加1。

　　在初始化时，把每个元素对应的rank初始化为1，同时set数组的初始化的值不再是-1，而是元素本身的值。以及在查找函数中，找到代表元素的条件需要改变。剩下的部分都基本相同。

　　有个问题就是，如果将路径压缩和按秩合并一起使用，很可能会破坏rank的准确性。

　　相应的代码如下：

 1 void initSet(int *set, int *rank, int n) {
 2     for (int i = 0; i < n; i++) {
 3         set[i] = i;
 4         rank[i] = 1;
 5     }
 6 }
 7
 8 int find(int *set, int x) {
 9     if (x == set[x]) return x;
10     else return set[x] = find(set, set[x]);
11 }
12
13 void merge(int *set, int rank, int x, int y) {
14     int x = find(set, x);
15     int y = find(set, y);
16     if (rank[x] <= rank[y]) {
17         set[x] = y;
18         if (rank[x] == rank[y] && x != y) rank[y]++;
19     }
20     else {
21         set[y] = x;
22     }
23 }

参考资料

　　算法学习笔记(1) : 并查集：https://zhuanlan.zhihu.com/p/93647900

　　并查集：https://www.cnblogs.com/cyjb/p/UnionFindSets.html