【算法图解】并查集：谁是你的老大

并查集（Union-Find / Disjoint Set Union, DSU）是一个非常“像人”的数据结构。

你可以把每个集合想成一个帮派：

每个人都有一个“老大”（代表元）
同一个帮派的人最终能找到同一个老大
两个帮派合并就是“认同一个老大”

它专门解决一类问题：动态连通性。

典型问题：

两个点是否连通？
连通块数量是多少？
加边过程中是否形成环？

1. 两个基本操作：find 与 union

并查集维护两个数组：

parent[x]：x 的父节点
rank/size：用于按秩合并（可选但强烈建议）

1.1 find：找老大

function find(x) {
  while (parent[x] !== x) x = parent[x]
  return x
}

1.2 union：合并两个集合

function union(a, b) {
  const ra = find(a)
  const rb = find(b)
  if (ra === rb) return false
  parent[rb] = ra
  return true
}

朴素版 union 会退化（像链表一样高）。

优化的关键是两招：

路径压缩
按秩/按大小合并

2. 路径压缩：让每个人直接认老大

路径压缩让 find 变得几乎“摊还 O(1)”。

递归写法最短：

function find(x) {
  if (parent[x] !== x) parent[x] = find(parent[x])
  return parent[x]
}

它会把 x 到老大路径上的所有节点都直接挂到老大下面。

3. 按秩合并：小树挂到大树

如果每次都把小树挂到大树，树的高度会很低。

这里用 size 实现：

function union(a, b) {
  let ra = find(a)
  let rb = find(b)
  if (ra === rb) return false

  if (size[ra] < size[rb]) {
    ;[ra, rb] = [rb, ra]
  }

  parent[rb] = ra
  size[ra] += size[rb]
  return true
}

4. 复杂度：为什么说它接近 O(1)？

路径压缩 + 按秩合并的并查集，单次操作的摊还复杂度是：

$O(\alpha(n))$

$\alpha(n)$ 是反阿克曼函数，增长极慢：

在宇宙尺度的 n 下也小于 5

所以工程里你可以近似认为：

find/union 都是“常数级”

5. 典型用法一：连通块数量

初始化每个点自成一派：

count = n

每 union 成功一次（两个集合合并）：

count--

最后 count 就是连通块数量。

6. 典型用法二：判断是否成环（无向图）

遍历每条边 (u, v)：

如果 find(u) === find(v)，说明 u 和 v 已经连通
再加这条边就会形成环

7. 典型用法三：最小生成树（Kruskal）

Kruskal 思想：

边按权重从小到大排序
依次尝试加入
如果会成环就跳过

“会成环吗？”这一步用并查集最省事。

8. 面试回答模板

并查集维护集合代表元，用 find/union 解决动态连通性。
通过路径压缩 + 按秩合并，把复杂度摊还到接近 O(1)。
常用于连通块计数、成环检测、Kruskal。

总结

并查集的核心不是代码量，而是两点：

find 要做路径压缩
union 要按秩/按大小

写对这两点，你的 DSU 就“又快又稳”。

【算法图解】并查集：谁是你的老大

相关标签