📚 并查集详解：从入门到 LeetCode 刷题实战

英文标题 / English Title: Union Find Explained: From Basics to LeetCode Problem Solving

来源 / Source: 程序员吴师兄 & Labuladong 的算法笔记

📌 文章简介 / Introduction

并查集（Disjoint Set Union, DSU）是一种看起来简单、真正理解却需要思考的数据结构。它在 LeetCode 中出现频率极高，尤其在连通性、集合合并类问题中几乎是标准解法。本文从基础讲起，深入讲解两个核心优化（路径压缩 + 按秩合并），并结合真题展示实战技巧。

Union Find (DSU) looks simple but requires deep understanding. It appears frequently in LeetCode, especially for connectivity and set-merging problems. This article covers the basics, two core optimizations (path compression + union by rank), and real problem-solving techniques.

👉 阅读原文: 并查集详解

🔍 内容要点 / Key Points

1. 并查集的核心思想

并查集本质上是维护多个不相交的集合，每个集合有一个代表元素（根节点）。通过”查”找根节点判断连通性，通过”并”合并不同集合。

两种基本实现：

• quick find：Find 很快 O(1)，Union 较慢 O(n)
• quick union：Union 较快，Find 较慢，需要优化

2. 两个核心优化

路径压缩（Path Compression）：在 Find 时，将路径上的所有节点直接指向根节点，大幅减少后续查询深度。

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # 递归压缩
    return self.parent[x]

按秩合并（Union by Rank）：合并时让深度小的树挂在深度大的树下，减少树的高度增长。

def union(self, x, y):
    if self.rank[x] < self.rank[y]:
        self.parent[x] = y
    elif self.rank[x] > self.rank[y]:
        self.parent[y] = x
    else:
        self.parent[y] = x
        self.rank[x] += 1

两个优化同时使用时，时间复杂度接近 O(α(n))，实际可视为 O(1)。

3. 经典应用模式

4. LeetCode 高频题型

💡 学习建议 / Learning Tips

1. 先理解思想再写代码：并查集代码很短，但背后的思想（树形结构表示集合）才是核心。
2. 两个优化缺一不可：只用一个优化，复杂度会退化；两个都用才能达到近似 O(1)。
3. 网格问题用一维坐标：将 (i, j) 映射为 i * cols + j，简化并查集在网格中的应用。
4. 朋友圈问题是模板：矩阵形式的连通分量问题，直接套用”初始化 → 遍历矩阵 union → 统计根数量”。
5. 带权并查集是进阶：如果面试中出现”相对关系”类问题（如食物链），带权并查集是必备技能。