在学习数据结构的过程中，有些概念听名字很高大上，但其背后的逻辑却异常接地气。并查集（Disjoint Set，也常被称为 Union-Find） 就是其中的典型代表。

如果你曾经被图论中复杂的连通性问题搞得焦头烂额，或者在刷 LeetCode 时遇到“朋友圈”、“岛屿数量”类的问题无从下手，那么这篇博客将帮你彻底拿下这个轻量级却极其强大的数据结构。

1. 什么是并查集？一个“认大哥”的故事

不要被“并查集”这三个字吓到。我们可以用一个非常现实的场景来理解它：江湖帮派。

假设江湖上有 $N$ 个大侠，一开始大家互不相识，每个人自成一派，自己就是自己的“大哥”。
后来，大家开始结交朋友：

• 查（Find）：当你想知道大侠 A 和大侠 B 是不是自己人时，你只需要问他们：“你们各自的终极大哥是谁？”如果他们的终极大哥是同一个人，那他们就是同一个帮派的。
• 并（Union）：大侠 A 和大侠 B 决定结盟，那么 A 的大哥就可以直接向 B 的大哥“臣服”（或者反过来），两个帮派就合并成了一个大帮派。

并查集，顾名思义，就是专门用来处理这种“合并（Union）”和“查找（Find）”操作的数据结构。

2. 核心操作与基础实现

并查集的底层通常使用一个一维数组 parent 来实现。parent[i] 存储的是元素 i 的父节点（也就是他的直接大哥）。

第一步：初始化 (Initialization)

一开始，每个人都是独立的，所以每个元素的父节点就是它自己。

class UnionFind:
    def __init__(self, size):
        # 初始时，每个人的大哥都是自己
        self.parent = [i for i in range(size)]

第二步：查找 (Find)

顺藤摸瓜，一直找到那个“大哥的大哥”（即 parent[i] == i 的根节点）。

    def find(self, i):
        # 如果自己就是大哥，返回自己
        if self.parent[i] == i:
            return i
        # 否则，继续找自己的父节点的大哥
        return self.find(self.parent[i])

第三步：合并 (Union)

找到两个元素的根节点，让其中一个根节点成为另一个根节点的子节点。

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            # i 的大哥臣服于 j 的大哥
            self.parent[root_i] = root_j

3. 进阶优化：如何让并查集飞起来？

虽然上面的基础版已经能跑了，但在极端情况下（比如每次合并都形成一条长长的链条），find 操作的时间复杂度会退化成 $O(n)$。为了保持高效，我们需要两大法宝：

法宝一：路径压缩 (Path Compression)

这是并查集的灵魂优化。既然我们每次 find 都要找终极大哥，那为什么不顺便在找的过程中，让这条路径上的所有小弟直接认终极大哥做父节点呢？这样下次再查就只需一步了！

代码只需要改动一行，非常优雅：

    def find_optimized(self, i):
        if self.parent[i] != i:
            # 递归寻找，并将沿途的所有节点直接指向根节点
            self.parent[i] = self.find_optimized(self.parent[i])
        return self.parent[i]

法宝二：按秩合并 (Union by Rank / Size)

在合并两个帮派时，为了防止树变得太深，我们总是倾向于把较小的帮派（树的高度低或节点少）合并到较大的帮派下。这就需要额外维护一个 rank 或 size 数组。在大多数算法竞赛和实际面试中，仅使用“路径压缩”就已经足够快了，按秩合并可以作为补充了解。

4. 复杂度分析

当你同时使用了路径压缩和按秩合并后，并查集的查询和合并操作的时间复杂度将接近常数级别：

• 时间复杂度：$O(\alpha(n))$。其中 $\alpha$ 是阿克曼函数的反函数。在宇宙范围内可观测的 $n$ 中，$\alpha(n)$ 不会超过 5。所以，你可以非常自信地认为它是 $O(1)$。
• 空间复杂度：$O(n)$，因为我们需要一个数组来存储每个元素的父节点。

5. 经典应用场景

掌握了并查集，以下这些问题对你来说将是降维打击：

1. 网络连通性问题：判断无向图中两点是否连通（如 LeetCode 547. 省份数量）。
2. 图的环检测：在无向图中，如果两个节点在添加边之前就已经属于同一个集合，那么添加这条边必定会形成环（如 LeetCode 684. 冗余连接）。
3. Kruskal 最小生成树算法：核心组件就是用并查集来判断加入最短边时是否会形成环。

结语

并查集的魅力在于它的代码极简，但背后蕴含的“分治”与“缓存（路径压缩）”思想却非常深刻。希望这篇文章能帮你把并查集纳入自己的知识武器库中！