并查集实战：用 Union-Find 解决连通性问题

用 DFS 刷 LeetCode 的“岛屿数量”这类题时，最让人难受的是每次遇到陆地都要重新遍历一遍，代码写起来虽然能过，但总觉得效率低得离谱。直到我真正搞明白并查集（Union-Find / DSU），才发现处理这种“两个点是否在同一个集合”的问题，根本不需要走那么远的路。

简单来说，并查集就是给每个元素找个“老大”（根节点）。如果两个元素的根节点一样，它们就属于同一个阵营。

这里有几个关键的优化点，没搞定这两个点，并查集就失去了灵魂：

• 路径压缩 (Path Compression)： 在执行 find 操作时，直接把路径上的所有节点都指向根节点。这样下次查询时，直接一步到位，不用再一层层往上爬。
• 按秩合并 (Union by Rank)： 合并两个集合时，总是把深度较小的树挂在深度较大的树下面，防止树退化成一条长链。

这两项优化结合后，时间复杂度几乎可以看作 $O(1)$，这在处理大规模图论问题时简直是神技。

下面是我习惯用的 Python 实现版本，重点在 find 的递归赋值和 union 的秩判断：

class UnionFind:
    def __init__(self, n):
        # 初始化时每个元素的父节点都是它自己
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # 核心优化：路径压缩
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX != rootY:
            # 核心优化：按秩合并，保持树的平衡
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False

在实操中，我踩过最深的坑就是忘记写 self.parent[x] = self.find(self.parent[x]) 而直接写 return self.find(self.parent[x])。虽然结果正确，但失去了路径压缩，在大数据量下直接导致 TLE（时间超限）。另外，合并前一定要先 find 出根节点，千万不要直接操作 parent[x] = y，否则会把整个集合结构搞乱。