「并查集」专题 4：并查集第 3 版 quick-union 基于 size 的优化
重点提示：这一版「并查集」代码是最基本的「并查集」，我们需要学习思想，核心思想是「代表元法」，以「树」的「根结点」作为代表元。
后续我们介绍这一版代码的两个优化：
1、按秩合并（有 2 个版本）
2、路径压缩（有 2 个版本）
介绍得多，只是为了方便大家建立知识结构，真正我们只会使用一个版本的「并查集」。我们放在介绍完了以后再说。
我们发现 union(4, 9) 与 union(9, 4) 其实是一样的，也就是把谁的根指向谁的根，这一点从正确性上来说是无关紧要的，但是对于 find 的时间复杂度就会有影响。为此，我们做如下优化。
在合并之前做判断，具体做法是，计算每一个结点有多少个元素直接或者间接地以它为根，我们应该将集合元素少的那结点的根指向集合元素多的那个结点的根。这样，形成的树就会更高概率地形成一棵层数较低的树。
为此，我们再引入一个 size 数组，size[i] 的定义是：以第 i 个结点为根的集合的元素的个数。
在初始化的时候 size[i] = 1，find 和 isConnected 操作中我们都不须要去维护 size 这个数组，唯独在 unionElements 的时候，我们才要维护 size 数组的定义。
Java 代码：
// union-find 算法的实现（加权 quick-union 算法）
public class UnionFind3 implements IUnionFind {
private int[] parent; // 第 i 个元素存放它的父元素的索引
private int count; // 连通分量的数量
private int[] size; // 以当前索引为根的树所包含的元素的总数
public UnionFind3(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
// 初始化时，所有的元素只包含它自己，只有一个元素，所以 size[i] = 1
size[i] = 1;
}
}
@Override
public String versionName() {
return "并查集的第 3 个版本，基于 parent 数组，quick-union，基于 size";
}
// 返回索引为 p 的元素的根结点的索引
@Override
public int find(int p) {
// 跟随链接找到根结点
while (p != parent[p]) {
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
return pRoot == qRoot;
}
@Override
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
// 这一步是与第 2 版不同的地方，我们不是没有根据地把一个结点的根结点的父结点指向另一个结点的根结点
// 而是将小树的根结点连接到大树的根结点
if (size[pRoot] > size[qRoot]) {
parent[qRoot] = pRoot;
size[pRoot] += size[qRoot];
} else {
parent[pRoot] = qRoot;
size[qRoot] += size[pRoot];
}
// 每次 union 以后，连通分量减 1
count--;
}
}
