「并查集」专题 3：并查集第 2 版基于 parent 的并查集（非最终版本）（非最终版本）
重点提示：这一版「并查集」代码是最基本的「并查集」，我们需要学习思想，核心思想是「代表元法」，以「树」的「根结点」作为代表元。
后续我们介绍这一版代码的两个优化：
1、按秩合并（有 2 个版本）
2、路径压缩（有 2 个版本）
介绍得多，只是为了方便大家建立知识结构，真正我们只会使用一个版本的「并查集」。我们放在介绍完了以后再说。
并查集第 2 版：quick-union
我们不再使用 id 数组，而使用 parent 数组，parent 数组的定义是：parent[i] 表示索引为 i 的结点的父亲结点的索引，在这个定义下，根结点的父亲结点是自己。
此时查询结点 p 和结点 q 相连这件事情，就是我们分别追溯 parent[p] 和 parent[q] （可以看到这样的过程很像在一棵树中的操作），查询到 parent[p] 和 parent[q] 的根结点，如果根结点相同，那么它们就同属于一个集合。
这样看来，find(int p) 好像费点劲，这也是我们接来下的几个并查集优化的方向，都是在 find(int p) 上做文章，但这保证了 union(int p, int q) 很快，我们只需把其中一个结点的父结点指向另一个结点的根结点（而谁的父结点指向谁的根结点，也是我们后几版并查集优化的方向），就完成了 union(int p, int q) 的操作。此时 union(int p, int q) 的操作只须要一行代码：
Java 代码：
parent[pRoot] = qRoot;初始化的时候，我们将每个元素都指向自己，此时表示这 $10$ 个结点互相之间没有连接关系。如下表所示：
上面的数组表示的并查集如下。
从正确性上来说，谁的根指向谁的根都是可以的。但是在实际运行的时候，我们发现，我们应该将层级较少的根指向层级较多的根，这样做是为了保证我们的并查集形成的树的高度不会增加，这样在 find 的时候，追溯的层数不会增加。我们在查找根的时候，应该使得查找的层数最少。
Java 代码：
public class UnionFind2 implements IUnionFind {
private int[] parent; // 第 i 个元素存放它的父元素的索引
private int count; // 连通分量的数量
public UnionFind2(int n) {
this.count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
@Override
public String versionName() {
return "并查集的第 2 个版本，基于 parent 数组，quick-union";
}
@Override
public int find(int p) {
// 跟随链接找到根结点
while (parent[p] != p) { // 只要不是根结点
p = parent[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
@Override
public void union(int p, int q) {
int pRoot = find(p); // 将 p 归并与之相同的分量中
int qRoot = find(q); // 将 q 归并与之相同的分量中
// 如果 p 和 q 已经在相同的分量之中，则什么都不做
if (pRoot == qRoot) {
return;
}
// 如果 parent[qRoot] = pRoot; 也是可以的，即将其中一个结点指向另一个结点
parent[pRoot] = qRoot;
// 每次 union 以后，连通分量减 1
count--;
}
}
