Skip to main content

并查集

番风April 30, 2025About 6 min

什么是并查集

朋友圈的表示方式

想象一个班级里的学生，随着时间的推移，学生们形成了不同的朋友圈。并查集就是用来跟踪这些朋友圈的工具。

每个朋友圈有一个 " 代表 "（老大）。如果我想知道两个学生是否在同一个朋友圈，只需要看他们的 " 老大 " 是否是同一个人。

初始化

开始时，每个学生独自形成一个朋友圈，自己是自己的老大。

# 初始化：每个人是自己的老大
def init(n):
    parent = [i for i in range(n)]
    return parent

Find 操作：查找老大

# 查找某人的老大
def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 路径压缩
    return parent[x]

路径压缩详解

路径压缩是并查集中一个重要的优化技巧。为了理解它，让我们先看看没有路径压缩时可能出现的问题。

问题场景

想象一个朋友圈的层级关系像一条长链：

  • 小明 → 小红 → 小刚 → 小李 → 小王

这里，箭头表示 " 认谁为老大 "。比如小明认小红为老大，小红认小刚为老大，以此类推。小王是整个朋友圈的最终老大。

当我们想知道小明的老大是谁时，需要沿着这条链一直查找：

小明 → 小红 → 小刚 → 小李 → 小王

这需要 4 步才能找到小王是最终老大。如果链更长，查找会更慢。

路径压缩的工作原理

路径压缩的核心思想是：既然我们已经知道小王是最终老大，为什么不让小明直接认小王为老大呢？

def find(parent, x):
    if parent[x] != x:  # 如果x不是自己的老大
        parent[x] = find(parent, parent[x])  # 找到x的最终老大，并让x直接指向它
    return parent[x]

当我们执行 find(parent, 小明) 时，会发生以下过程：

  1. 检查小明的老大是不是自己 → 不是，是小红
  2. 递归调用 find(parent, 小红)
    • 检查小红的老大是不是自己 → 不是，是小刚
    • 递归调用 find(parent, 小刚)
      • 检查小刚的老大是不是自己 → 不是，是小李
      • 递归调用 find(parent, 小李)
        • 检查小李的老大是不是自己 → 不是，是小王
        • 递归调用 find(parent, 小王)
          • 检查小王的老大是不是自己 → 是的，返回小王
        • 设置小李的老大为小王（压缩）
      • 设置小刚的老大为小王（压缩）
    • 设置小红的老大为小王（压缩）
  3. 设置小明的老大为小王（压缩）

执行完这个递归过程后，朋友圈的结构变成了：

小明 → 小王
小红 → 小王
小刚 → 小王
小李 → 小王
小王 → 小王

现在，所有人都直接指向小王作为老大，形成了一个 " 扁平 " 的结构。下次再查找任何人的老大，都只需要一步就能找到。

图解

原始结构：

小明 → 小红 → 小刚 → 小李 → 小王

路径压缩后：

     小明
     │
     ↓
小红 → 小王 ← 小李
     ↑
     │
    小刚

实际代码解释

def find(parent, x):
    if parent[x] != x:  # 如果x不是自己的老大
        parent[x] = find(parent, parent[x])  # 递归找到最终老大，并更新x的老大为最终老大
    return parent[x]  # 返回x的老大

这个递归过程实现了路径压缩：当我们查找某人的老大时，不仅返回最终老大，还会顺便让路径上的每个人都直接认最终老大为自己的老大。

路径压缩使得查找操作的平均时间复杂度接近于 O(1)，大大提高了并查集的效率。

Union 操作：合并朋友圈

# 合并两个朋友圈
def union(parent, x, y):
    root_x = find(parent, x)
    root_y = find(parent, y)
    if root_x != root_y:
        parent[root_y] = root_x  # y的老大认x的老大为新老大


当我们查找某人的老大时，顺便更新路径上每个人的老大，使得下次查找更快

让小朋友圈并入大朋友圈，而不是反过来

应用场景

网络连通性：判断网络中的计算机是否连通
环检测：判断图中是否有环
迷宫生成：生成迷宫的随机算法
最小生成树：Kruskal 算法的核心部分

完整示例

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(x, y, parent, rank):
		rootx = find(x, parent)
		rooty = find(y, parent)
		if(rootx == rooty):
			return;
		if rank[rootx]>rank[rooty]: 
			parent[rooty] = rootx
		elif rank[rooty]>rank[rootx]:
			parent[rootx] = rooty
		else:
			parent[rooty] = rootx
			rank[rootx]+=1
		return (parent, rank)

Leetcode

omnifocus归并集

基础题目

  1. 547. 省份数量 - 经典的并查集入门题
    20250430 一刷
  2. 200. 岛屿数量 - 可以用 DFS/BFS 或并查集解决
    20250501 一刷
  3. 128. 最长连续序列 - 可用并查集优化
    20250501 一刷
  4. 990. 等式方程的可满足性
    20250501 一刷

中等题目

  1. 721. 账户合并 - 实际应用场景
  2. 684. 冗余连接 - 在图中寻找环
  3. 1319. 连通网络的操作次数
  4. 959. 由斜杠划分区域
  5. 685. 冗余连接 II - 有向图版本
  6. 1202. 交换字符串中的元素

进阶题目

  1. 765. 情侣牵手
  2. 952. 按公因数计算最大组件大小
  3. 803. 打砖块 - 需要逆向思维
  4. 1632. 矩阵转换后的秩 - 结合排序和并查集
  5. 778. 水位上升的泳池中游泳 -

omnifocus:///paste?content=

- 工作
	- 04 Coding&Tech/04 Coding Ability @parallel(true) @autodone(false)
		obsidian://open?vault=notes&file=04%20Coding%20%26%20Tech%2F04%20Coding%20Ability%2F04%20Coding%20Ability

		- 并查集 @parallel(false) @autodone(false) @repeat-method(due-after-completion) @repeat-rule(FREQ=MONTHLY)
			obsidian://open?vault=notes&file=04%20Coding%20%26%20Tech%2F04%20Coding%20Ability%2F00%20Leetcode%2F%E4%B8%93%E9%A2%98%2F%E5%B9%B6%E6%9F%A5%E9%9B%86

			- 547. 省份数量 @parallel(true) @autodone(false)
				547. 省份数量](https://leetcode.com/problems/number-of-provinces/)** - 经典的并查集入门题 
				   20250430 一刷

			- 200. 岛屿数量 @parallel(true) @autodone(false)
				200. 岛屿数量](https://leetcode.com/problems/number-of-islands/)** - 可以用 DFS/BFS 或并查集解决

			- 128. 最长连续序列 @parallel(true) @autodone(false)
				128. 最长连续序列](https://leetcode.com/problems/longest-consecutive-sequence/)** - 可用并查集优化

			- 990.Satisfiability of Equality Equations @parallel(true) @autodone(false)
				[Satisfiability of Equality Equations - LeetCode](https://leetcode.com/problems/satisfiability-of-equality-equations/description/)

			- 721.账户合并 @parallel(true) @autodone(false)
				账户合并(https://leetcode.com/problems/accounts-merge/)** - 实际应用场景

			- 684. 冗余连接  @parallel(true) @autodone(false)
				**[684. 冗余连接](https://leetcode.com/problems/redundant-connection/)** - 在图中寻找环

			- 1319. 连通网络的操作次数 @parallel(true) @autodone(false)
				**[1319. 连通网络的操作次数](https://leetcode.com/problems/number-of-operations-to-make-network-connected/)**

			- 959. 由斜杠划分区域 @parallel(true) @autodone(false)
				**[959. 由斜杠划分区域](https://leetcode.com/problems/regions-cut-by-slashes/)**

			- 685. 冗余连接 II @parallel(true) @autodone(false)
				**[685. 冗余连接 II](https://leetcode.com/problems/redundant-connection-ii/)** - 有向图版本

			- 1202. 交换字符串中的元素 @parallel(true) @autodone(false)
				**[1202. 交换字符串中的元素](https://leetcode.com/problems/smallest-string-with-swaps/)**
Default footer
Copyright © 2026 番风