← 上一课第 28 课 / 34下一课 →

🔗 并查集 — 联合与查找的魔法

连通性的终极武器，近O(1)判断两个元素是否属于同一集合

📖 并查集的核心概念

并查集（Union-Find / Disjoint Set Union, DSU）是一种树形数据结构，用于处理不相交集合的合并与查询。它支持两个核心操作：find（查找元素所属集合的代表）和 union（合并两个集合）。凭借路径压缩和按秩合并，单次操作接近 O(1)。

并查集的工作原理: 初始: 每个元素自成一个集合 0 1 2 3 4 5 ↓ ↓ ↓ ↓ ↓ ↓ [0][1][2][3][4][5] parent[i] = i union(0,1): 0和1合并 union(2,3): 2和3合并 0 1 2 3 4 5 ↓↗ ↓↗ ↓ ↓ [0] [2] [4][5] union(1,3): 合并0和2的集合 0 1 2 3 4 5 ↓↗ ↗↗ ↓ ↓ [0] [4][5] find(3) → 找到根0 (路径压缩后3直接指向0)

1. 两个关键优化

路径压缩：在 find 操作时，将路径上的所有节点直接指向根节点。递归实现最简洁：parent[x] = find(parent[x])。这使得后续查询更快，树高度趋近1。
按秩合并：在 union 时，将较小的树合并到较大的树下。用 rank 数组记录树的高度，避免树退化成链表。与路径压缩结合后，单次操作均摊 O(α(n))，α 是反阿克曼函数，可视为常数。

2. Python 并查集模板

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)
面试时，先把模板写出来（或默写），然后根据题目修改。常见变体：维护集合大小、维护到根的距离、维护集合的最值。模板中 count 记录连通分量数，很多题目直接用。

🎯 题目一：岛屿数量 (LC 200) — 并查集版

题目描述：用并查集重新解决岛屿数量问题。遍历网格，将相邻的陆地合并，最终统计连通分量数。

并查集解法思路: 1 1 0 0 0 1 1 0 0 0 遍历每个'1': 0 0 1 0 0 只向右和向下合并(避免重复) 0 0 0 1 1 合并过程: (0,0)-(0,1) (0,0)-(1,0) (1,0)-(1,1) (2,2) 独立 (3,3)-(3,4) 最终3个连通分量 → 3个岛屿

思路分析

遍历+合并：将二维坐标映射为一维索引。遍历网格，遇到 '1' 只向右和向下检查，如果邻居也是 '1' 则合并。最后统计连通分量数（parent 等于自己的数量）。

代码实现

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        rows, cols = len(grid), len(grid[0])
        uf = UnionFind(rows * cols + 1)  # +1 给水域用
        water = rows * cols  # 水域的虚拟节点
        
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1':
                    idx = r * cols + c
                    # 向右和向下合并
                    if r + 1 < rows and grid[r+1][c] == '1':
                        uf.union(idx, (r+1) * cols + c)
                    if c + 1 < cols and grid[r][c+1] == '1':
                        uf.union(idx, r * cols + c + 1)
                else:
                    # 水域连接到虚拟节点
                    uf.union(r * cols + c, water)
        
        return uf.count - 1  # 减去水域虚拟节点

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
        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

复杂度分析

时间复杂度：O(m×n×α(m×n)) ≈ O(m×n)

空间复杂度：O(m×n)

并查集和 DFS 都能解决岛屿数量。DFS 更直观，并查集在需要动态合并（如 LC 827 最大人工岛）时更有优势。面试时两种方法都要掌握。

🎯 题目二：省份数量 (LC 547)

题目描述：有 n 个城市，给定 n×n 的邻接矩阵 isConnected，如果 isConnected[i][j]=1 表示城市 i 和 j 直接相连。省份是一组直接或间接相连的城市。返回省份数量。

示例: isConnected = [[1,1,0],[1,1,0],[0,0,1]] 城市: 0 ↔ 1, 2 独立 省份1: {0, 1} 省份2: {2} 答案: 2

思路分析

标准并查集：遍历邻接矩阵的上三角（i < j），如果 isConnected[i][j]=1 则 union(i, j)。最终统计不同的根节点数量 = 省份数。

代码实现

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        n = len(isConnected)
        parent = list(range(n))
        rank = [0] * n
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py: return
            if rank[px] < rank[py]: px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]: rank[px] += 1
        
        for i in range(n):
            for j in range(i + 1, n):
                if isConnected[i][j] == 1:
                    union(i, j)
        
        return len(set(find(i) for i in range(n)))

复杂度分析

时间复杂度：O(n²·α(n)) ≈ O(n²)（遍历矩阵）

空间复杂度：O(n)

注意：LC 547 的邻接矩阵是直接连接关系，省份是传递闭包。城市 A 连 B，B 连 C，则 A、B、C 属于同一省份。并查集天然处理传递性。

🎯 题目三：冗余连接 (LC 684)

题目描述：一棵树有 n 个节点（无环无向图），多加一条边后变成有环图。给定这 n 条边的图，删除一条边使图变回树。返回最后出现的那条冗余边。

示例: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]] 1 ── 2 1 ── 2 │ │ 删除[1,4] │ │ 4 ── 3 →→→ 4 ── 3 │ │ 5 5 冗余边: [1,4] (构成环1-2-3-4-1的最后一条边)

思路分析

并查集检测环：依次加入每条边，如果 union(u, v) 返回 False（u 和 v 已在同一集合），说明这条边会形成环，即为冗余边。
为什么返回最后出现的冗余边？因为按顺序遍历，题目要求返回最后出现的。如果有多个冗余边，最后检测到的就是答案。

代码实现

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        parent = list(range(n + 1))
        rank = [0] * (n + 1)
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x, y):
            px, py = find(x), find(y)
            if px == py:
                return False  # 已连通，形成环
            if rank[px] < rank[py]: px, py = py, px
            parent[py] = px
            if rank[px] == rank[py]: rank[px] += 1
            return True
        
        for u, v in edges:
            if not union(u, v):
                return [u, v]
        return []

复杂度分析

时间复杂度：O(n·α(n)) ≈ O(n)

空间复杂度：O(n)

LC 684 是无向图，LC 685 是有向图版本的冗余连接，难度更高。684 用并查集很直观，685 需要讨论入度和环的类型。

🔬 并查集的进阶技巧

掌握基础的 find/union 后，并查集还有几个进阶变体：

1. 维护集合大小

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n  # 每个集合初始大小为1
    
    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
        if self.size[px] < self.size[py]: px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]  # 更新大小

2. 带权并查集（维护到根的距离）

# 示例: LC 399 除法求值
# 维护节点到根的权重比值
class WeightedUF:
    def __init__(self, n):
        self.parent = list(range(n))
        self.weight = [1.0] * n  # 到根的权重
    
    def find(self, x):
        if self.parent[x] != x:
            orig = self.parent[x]
            self.parent[x] = self.find(self.parent[x])
            self.weight[x] *= self.weight[orig]
        return self.parent[x]

3. 可撤销并查集

标准并查集的路径压缩是不可撤销的。如果需要回溯（如回溯法中撤销合并），使用按秩合并但不用路径压缩，配合栈记录操作历史。

并查集的常见误区：(1) 只用路径压缩或只用按秩合并，效果不如两者结合；(2) 忘记处理 parent[i]=i 的初始化；(3) find 后没有用返回值而是重复查找。
成就解锁：联合大师 — 掌握并查集标准模板、连通分量统计、环检测三大核心应用
LeetCode AC验证：LC 200 Number of Islands (UF) ✅ | LC 547 Number of Provinces ✅ | LC 684 Redundant Connection ✅

📝 课后练习

  1. LC 685 冗余连接 II（有向图版本，高难度）
  2. LC 827 最大人工岛（并查集+枚举翻转）
  3. LC 990 等式方程的可满足性（并查集判断等式冲突）
  4. LC 399 除法求值（带权并查集）
  5. LC 721 账户合并（并查集+哈希表）

🔑 本课要点回顾

📚 扩展阅读

思考题：如果不使用路径压缩和按秩合并，最坏情况下并查集的 find 操作复杂度是多少？提示：不优化的并查集可能退化为链表，find 变为 O(n)。