第 2 版基于 quick-union 实现（非最终版本）

重点：这一版「并查集」代码是最基本的「并查集」，我们需要学习思想，核心思想是「代表元法」，以「树」的「根结点」作为代表元。

后续我们介绍这一版代码的两个优化：

• 按秩合并（有 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;

初始化的时候，我们将每个元素都指向自己，此时表示这 个结点互相之间没有连接关系。如下表所示：

上面的数组表示的并查集如下。

从正确性上来说，谁的根指向谁的根都是可以的。但是在实际运行的时候，我们发现，我们应该将层级较少的根指向层级较多的根，这样做是为了保证我们的并查集形成的树的高度不会增加，这样在 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--;
    }
}

---

作者：liweiwei1419 链接：https://suanfa8.com/union-find/quick-union 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。