并查集

本章目标：掌握并查集的路径压缩与按秩合并，解决连通性问题。

你将学到

• 并查集的核心思想
• 路径压缩优化
• 按秩合并优化
• 连通分量计数
• 动态连通性判断

1. 概念

并查集（Union-Find / Disjoint Set Union）是一种用于管理不相交集合的数据结构。它支持两种操作：

• find(x)：查找元素 x 所属集合的代表元素（根）
• union(x, y)：合并 x 和 y 所在的两个集合

核心思想：用一个数组 parent 表示森林，parent[i] 是 i 的父节点。根节点的 parent 指向自己。两个元素属于同一集合当且仅当它们的根相同。

朴素并查集的 find 和 union 最坏 O(n)，但通过两个优化可以达到近乎 O(1) 的均摊复杂度：

• 路径压缩：find 时把路径上所有节点直接连到根
• 按秩合并：总是把矮树接到高树上

2. 核心模板

标准并查集实现

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = 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):
        """按秩合并"""
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # 已在同一集合
        # 矮树接高树
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

复杂度

• find/union：均摊 O(α(n))，α 是反阿克曼函数，n < 10⁸ 时 α < 5
• 空间：O(n)

3. 经典题目精讲

LeetCode 200 · 岛屿数量（并查集解法）

题意：统计二维网格中岛屿数量。

思路：把每个 '1' 格子作为一个元素，相邻的 '1' 合并。

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)

    # 将每个陆地与右边和下面的陆地合并
    water_count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '0':
                water_count += 1
                continue
            idx = r * cols + c
            # 向右
            if c + 1 < cols and grid[r][c+1] == '1':
                uf.union(idx, r * cols + c + 1)
            # 向下
            if r + 1 < rows and grid[r+1][c] == '1':
                uf.union(idx, (r+1) * cols + c)

    # 连通分量数 = 总格子数 - 水格子数 后的连通分量
    roots = set()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                roots.add(uf.find(r * cols + c))
    return len(roots)

LeetCode 547 · 省份数量

题意：给定城市连接矩阵，求省份（连通分量）数量。

思路：直接并查集，合并相连的城市。

def findCircleNum(isConnected):
    n = len(isConnected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if isConnected[i][j]:
                uf.union(i, j)
    return uf.count

LeetCode 684 · 冗余连接

题意：一棵树多了一条边，找到那条可以删去的边。

思路：逐条加边，当 union 返回 False（已在同一集合）时，这条边就是冗余的。

def findRedundantConnection(edges):
    n = len(edges)
    uf = UnionFind(n + 1)
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]
    return []

LeetCode 990 · 等式方程的可满足性

题意：给定方程列表（== 或 !=），判断是否可满足。

思路：先处理所有 == 方程做 union，再检查 != 方程的两端是否在同一集合。

def equationsPossible(equations):
    uf = UnionFind(26)
    # 先处理 ==
    for eq in equations:
        if eq[1] == '=':
            u = ord(eq[0]) - ord('a')
            v = ord(eq[3]) - ord('a')
            uf.union(u, v)
    # 再检查 !=
    for eq in equations:
        if eq[1] == '!':
            u = ord(eq[0]) - ord('a')
            v = ord(eq[3]) - ord('a')
            if uf.connected(u, v):
                return False
    return True

4. 易错点

• ⚠️ parent 数组初始化时每个元素指向自己
• ⚠️ 路径压缩和按秩合并可以同时使用，rank 不再精确但够用
• ⚠️ 二维网格映射到一维时下标计算 r * cols + c 不要搞混行列
• ⚠️ 统计连通分量数时用 count 变量比遍历所有根更高效

5. 推荐刷题清单

题号	题名	难度	关键
200	岛屿数量	Medium	并查集
547	省份数量	Medium	连通分量
684	冗余连接	Medium	找环边
721	账户合并	Medium	字符串并查集
990	等式方程可满足性	Medium	先等后不等
1319	连通网络的操作次数	Medium	连通分量

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS) 第 21 章