引言

并查集（Disjoint Set Union，简称DSU）是一种用于处理一些不交集的合并及查询问题。它主要支持两种操作：查找（Find）和合并（Union）。

查找：确定某个元素属于哪一个子集。它可以用来确定两个元素是否属于同一子集。
合并：将两个子集合并成一个集合。
由于其实现简单、效率高，并查集被广泛应用于网络连接性问题、图像处理、社交网络分析等多个领域。本文将逐步介绍并查集的基本实现，并探讨其优化方法。

使用场景

并查集广泛应用于以下场景：

1. 连通性问题：判断图中两个节点是否连通。例如，给定一张图，我们可以使用并查集来快速判断图中任意两点是否连通，或者计算整个图有多少个连通分量等。

2. 最小生成树算法：如最小生成树Kruskal算法中用于判断是否形成环。

3. 网络连接问题：判断网络中的两个节点是否连接。

4. 社交网络：判断两个人是否属于同一个社交圈。

5. 图像处理：图像处理中，用于连通区域标记。通过将相邻像素视为元素，并根据它们的颜色或灰度值决定是否合并，可以有效地识别出图像中的各个独立区域。

案例分析

如图所示，0到9的10个数字，每个数字可以表示一个节点，节点之间可以连接起来，成为一个连通分量。我们需要一个数据结构，能够判断两个节点是否属于同一个连通分量（find），同时还可以把两个连通分量连在一起，形成一个更大的连通分量（union）

方案一quick-find

思路分析

我们可以考虑使用Map实现，其中key为节点的值，value为所在连通分量的标识。对于find方法直接使用get即可，而union方法，则需要将两个连通分量的标识统一即可，即找到两个节点的连通分量标识p和q, 将所有value=p的值替换为q(或者q替换为p）

实现步骤如图所示

代码实现

这里使用数组代替map， 数组下表对应的节点的值，数组的value为连通分量标识

package uf;public class UnionFind {// 连通分量标识private final int[] parent;public UnionFind(int size) {parent = new int[size];}private int find(int n) {return parent[n];}private void union(int p, int q) {int rootP = find(p);int rootQ = find(q);// 更新p的连通分量标识为qif (rootP != rootQ) {for (int i = 0; i < parent.length; i++) {if (parent[i] == rootP) {parent[i] = rootQ;}}}}public static void main(String[] args) {UnionFind uf = new UnionFind(10);for (int i = 0; i < uf.parent.length; i++) {uf.parent[i] = i;}uf.union(4, 3);int uf4 = uf.find(4);int uf3 = uf.find(3);int uf8 = uf.find(8);System.out.println("uf4的parent: " + uf4 + ", uf3的parent:" + uf3 + ", uf8的parent:" + uf8);uf.union(3, 8);uf4 = uf.find(4);uf3 = uf.find(3);uf8 = uf.find(8);System.out.println("uf4的parent: " + uf4 + ", uf3的parent:" + uf3 + ", uf8的parent:" + uf8);}
}

结果如下

复杂度分析

• 查找操作（Find）：时间复杂度为O(1)，因为我们直接访问数组中的元素。

• 合并操作（Union）：时间复杂度为O(n)，因为我们需要遍历整个数组来更新所有属于某个集合的元素。

方案二 quick-union

思路分析

代码实现

代码实现

package uf;public class UnionFind {// 父节点private final int[] parent;// 各个根节点所对应的分量的大小private final int[] size;public UnionFind(int size) {parent = new int[size];this.size = new int[size];}private int find(int n) {// 根节点的parent指向自己while (n != parent[n]) {// 不断向上查找父节点n = parent[n];}return n;}private void union(int p, int q) {int rootP = find(p);int rootQ = find(q);if (rootP != rootQ) {// 将分量较大的根节点指向分量较小的根节点if (size[p] < size[q]) {parent[rootP] = rootQ;size[rootQ] += size[rootP];} else {parent[rootQ] = rootP;size[rootP] += size[rootQ];}}}public static void main(String[] args) {UnionFind uf = new UnionFind(10);for (int i = 0; i < uf.parent.length; i++) {uf.parent[i] = i;}uf.union(4, 3);int uf4 = uf.find(4);int uf3 = uf.find(3);int uf8 = uf.find(8);System.out.println("uf4的parent: " + uf4 + ", uf3的parent:" + uf3 + ", uf8的parent:" + uf8);uf.union(3, 8);uf4 = uf.find(4);uf3 = uf.find(3);uf8 = uf.find(8);System.out.println("uf4的parent: " + uf4 + ", uf3的parent:" + uf3 + ", uf8的parent:" + uf8);}
}

可以看到结果是将小树的根连到了大树的根上

复杂度分析

• 查找操作（Find）：时间复杂度为O(log n)，因为加权规则使得树的高度保持在O(log n)级别（这里不做证明，可以参考算法第四版）

• 合并操作（Union）：时间复杂度为O(log n)，与查找操作相同。

加权树实现显著提高了并查集的效率，尤其是在处理大规模数据时。但是能不能让find方法的复杂度像quick-find一样快呢？

方案四 路径压缩

思路分析

我们尝试结合quick-find的扁平的数据结构，以及加权quick-union的平衡树的结构。在find方法中，在节点向上查询的过程中，顺便将路径中的节点的父节点指向root，这种操作叫做路径压缩。这样后续的find操作，对于压缩过路径的连通分量来说，可以使得树更扁平，提高find的效率。

假设我们有如下树结构

1
|  \
2   3
       \
        4

当我们调用 find(4) 时，路径压缩会将节点 4、3、2 直接指向根节点 1。
压缩后的树结构变为：

          1
        /  |  \   
      2  3   4

代码实现

这里是需要修改find方法，递归地修改每个父节点的parent

    private int find(int n) {while (n != parent[n]) {// 递归地将路径上的所有节点指向根节点parent[n]= find(parent[n]);}return n;}

 复杂度分析

• 查找操作（Find）：时间复杂度接近O(1)，因为路径压缩使得树的高度几乎为常数。

• 合并操作（Union）：时间复杂度接近O(1)，与查找操作相同。

总结

并查集是一种非常高效的数据结构，适用于处理不相交集合的合并与查找问题。通过从数组到树结构，再到加权树和路径压缩的演进，我们不断优化了并查集的性能。最终，路径压缩技术使得并查集的操作时间复杂度接近O(1)，非常适合处理大规模数据。