本文内容为数据结构并查集（DSU）的介绍与实现，详细讲解了并查集这一数据结构所能实现的各种操作，以及如何通过路径压缩与按秩合并大幅优化并查集的效率。

1. 并查集

1.1 介绍及其基础操作

并查集（Disjoint Set Union，DSU，也称为不相交集合）是一种用于管理一组不相交集合的数据结构。它支持以下两种主要操作：

• 查找（Find）：确定某个元素属于哪个集合。
• 合并（Union）：将两个集合合并为一个集合。

并查集在解决动态连通性问题（如网络连接、图的连通分量、最小生成树等）时非常高效。

并查集中的每个集合有一个代表元（也成为根节点），用于标识该集合。并查集通常使用数组或树来表示，每个元素存储其父节点的引用，根节点的父节点指向自己。

（1）初始化

假设有6个元素：{0, 1, 2, 3, 4, 5}，初始时每个元素都是一个独立的集合，即每个元素的父节点是它自己，我们用 pre[i] 表示第 $i$ 个节点的父节点，那么初始化时 pre 的内容如下：

java">pre = [0, 1, 2, 3, 4, 5]

（2）Find

查找操作的实现思路是从当前元素开始，沿着父节点逐级向上查找，直到找到根节点（每个集合中父节点指向自己的节点就是这个集合的根节点），该算法 find(x) 返回的即为节点 $x$ 所在集合的根节点序号。

例如当前的 pre 数组为 pre = [0, 1, 1, 2, 5, 3]，那么查找5号节点所属集合的算法流程如下：

• 执行 find(5)，由于 pre[5] = 3，因此5号节点不是根节点，继续查找3号节点也就是其父节点所在的集合；
• 执行 find(3)，由于 pre[3] = 2，因此3号节点不是根节点，继续查找2号节点所在的集合；
• 执行 find(2)，由于 pre[2] = 1，因此2号节点不是根节点，继续查找1号节点所在的集合；
• 执行 find(1)，由于 pre[1] = 1，因此1号节点是整个集合的根节点，最后查找算法返回1。

我们用递归的思想可以很容易实现查找操作（先用 C++ 演示）：

int find(int k) {if (pre[k] == k) return k;return find(pre[k]);
}

有了 Find 操作后我们想判断两个节点 $x,y$ 是否连通（在同一个集合中）就很简单了，即判断 find(x) 是否等于 find(y)。

（3）Union

合并操作的实现思路是找到两个元素的根节点，然后将其中一个根节点的父节点指向另一个根节点，很容易实现：

void union(int x, int y) {int px = find(x), py = find(y);if (px != py) pre[px] = py;
}

1.2 路径压缩

为了提高并查集的效率，通常会使用两种优化技术分别为路径压缩（Path Compression）与按秩合并（Union by Rank）。

路径压缩的实现思路是在 Find 操作中，将查找路径上的所有节点直接指向最后的根节点，从而减少后续查找的时间，即在递归查找的同时递归地将每个节点的父节点更新为根节点：

int find(int k) {if (pre[k] == k) return k;return pre[k] = find(pre[k]);
}

假设当前父节点数组为 pre = [0, 1, 1, 2, 5, 3]，那么在执行完一次 find(5) 后该数组的内容就更新为 pre = [0, 1, 1, 1, 5, 1]，这样之后如果还要继续查询3号节点或5号节点所在的集合时就不用在递归查找好几次了。

结合图片来理解一下，在下面这样的并查集结构下我们想查看10与15是否相连，那么我们便执行了 find(10) 与 find(15)，执行 Find 操作时沿着蓝色的路径一路向根节点查询：

使用路径压缩后我们将查询时一路上走过的节点都更新其父节点为根节点，那么更新后的并查集就变成了下面这样，能够有效地优化整棵树的深度：

在没有路径压缩的情况下，Find 操作的时间复杂度取决于树的深度。最坏情况下，如果所有元素都依次合并成一条链（即树的高度为 $n$，其中 $n$ 是元素的数量），则每次查找最末尾的那个元素都需要遍历整个链，时间复杂度为 $O(n)$，若有 $m$ 次查找，则时间复杂度为 $O(nm)$。

路径压缩显著减少了查询后树的高度，未来的查询会变得非常快，在进行多次操作后，路径压缩导致树的高度趋向于非常小（通常为 $O(logn)$），且查找操作的时间复杂度会接近 $O(\alpha (n))$，其中 $\alpha (n)$ 是阿克曼函数的反函数，它是一个非常缓慢增长的函数，可以认为是常数时间复杂度，即 $O(\alpha (n))\approx O(1)$。

1.3 按秩合并

按秩合并的实现思路是在 Union 操作中，将较小的树合并到较大的树中，从而避免树的高度过高，我们可以用 rank[] 数组来记录每个集合的秩（或高度），用于按秩合并操作，每个集合的秩初始化为1，在 Union 操作中如果两棵树的秩相同，则合并后将根节点的秩加一：

void connect(int x, int y) {int px = find(x), py = find(y);if (px != py) {if (rk[px] < rk[py]) pre[px] = py;else if (rk[px] > rk[py]) pre[py] = px;else pre[px] = py, rk[py]++;}
}

由于在 C++ 中 union 与 rank 已经是关键字了，因此此处我们将其分别改为 connect 与 rk。

2. Java实现DisjointSetUnion

经过前面的讲解，现在使用 Java 自己实现一个完整的并查集 DisjointSetUnion 就很简单了，只需要将所有方法组合在一起就是完整的并查集数据结构：

java">package CS61B.Lecture14;public class DisjointSetUnion {private int[] parent;private int[] rank;/*** 构造函数：初始化并查集* @param size 元素数量*/public DisjointSetUnion(int size) {parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;rank[i] = 1;}}/*** 查找操作（带路径压缩）* @param x 要查找的元素* @return 元素 x 的根节点（集合代表）*/public int find(int x) {if (parent[x] != x) parent[x] = find(parent[x]);return parent[x];}/*** 合并操作（带按秩合并）* @param x 元素 x* @param y 元素 y*/public void union(int x, int y) {int px = find(x), py = find(y);if (px != py) {if (rank[px] < rank[py]) parent[px] = parent[py];else if (rank[px] > rank[py]) parent[py] = parent[px];else {parent[px] = py;rank[py]++;}}}/*** 检查两个元素是否属于同一集合* @param x 元素 x* @param y 元素 y* @return true 如果属于同一集合，否则 false*/public boolean isConnected(int x, int y) {return find(x) == find(y);}public static void main(String[] args) {DisjointSetUnion dsu = new DisjointSetUnion(5);dsu.union(0, 2);dsu.union(2, 3);dsu.union(1, 4);  // 此时并查集为：[{0, 2, 3}, {1, 4}]System.out.println(dsu.isConnected(0, 3));  // trueSystem.out.println(dsu.isConnected(3, 4));  // falseSystem.out.println(dsu.isConnected(1, 4));  // true}
}

这次我们将 Find 操作的代码用另外一种等价的形式写一遍，只是这种写法可能有人容易踩坑，就是最后返回的时候写成 return x; 这是不对的，因为只有对于根节点来说是满足 parent[x] == x 的，而且其 parent 数组中的值不会做更新，在递归回溯的时候所有子节点的 parent 会被更新，更新为从根节点逐级回溯来的值，因此最后需要返回根节点的值 parent[x]，而不是返回当前节点 x。