illegalCreed

中文

English

中文

English

Appearance

入门：不相交集合、parent 数组与 find/union ​

基于通用数据结构概念 · 核于 2026-07

速查 ​

  • 定义：并查集（Union-Find / DSU）是一种管理一组不相交集合的树型结构，只支持两个操作——find（查某元素属于哪个集合）和 union（合并两个集合）。
  • 核心思想：用一棵树表示一个集合，树根（代表元）标识这个集合；判断两元素是否同类 = 看它们的根是否相同。
  • parent 数组：parent[i] 存 i 的父节点；根节点 parent[root] == root（自指）——这是「我是根」的标志。
  • 初始化：每个元素自成一组，parent[i] = i（自己是自己的根），共 n 个独立集合。
  • find(x)：沿 parent 一直往上找，直到 parent[x] === x（根），返回根——即 x 所属集合的代表元。
  • union(x, y)：先 find(x)、find(y) 找到两个根；若根相同说明已同组（无需合并）；若不同，把一棵树的根挂到另一棵树的根下（parent[rootX] = rootY）。
  • 判断同组：find(x) === find(y)——这是并查集最高频的用法（判连通、判等价）。
  • 朴素复杂度：find/union 最坏 O(n)（树退化成链）；加了路径压缩 + 按秩/按大小合并后均摊 O(α(n)) ≈ O(1)。
  • 典型应用：连通分量个数、Kruskal 最小生成树（判环）、朋友圈/岛屿等价类、动态连通性、无向图判环。
  • 只合不分：并查集只支持合并，不支持拆分；要拆分得用「可撤销/回滚并查集」。
  • 进阶顺序：路径压缩与按秩合并 → 工程应用 → 参考。

一、不相交集合：什么是并查集 ​

并查集解决的核心问题是：给定一堆元素，它们被分成若干「互不相交」的组，如何高效地「查某元素属于哪组」和「合并两组」。

举个生活化的例子——「朋友圈」：n 个人，已知若干对「朋友关系」（朋友的朋友也是朋友），问任意两人是否在同一个朋友圈、共有多少个朋友圈。这就是典型的等价类合并问题，并查集的拿手好戏。

关键约定：

  • 每个集合用一棵树表示。
  • 树的根节点作为这个集合的代表元（representative）——同一个集合里所有元素的根都相同，根就是「身份证」。
  • 判断「x 和 y 是否同集合」= find(x) === find(y)（根相同则同集合）。

注意「不相交」的含义：一个元素只能属于一个集合——合并后原来的两个集合就合成一个了，不存在「重叠」。

二、parent 数组：一棵树的表示 ​

并查集不需要真的构造树节点（没有左右子指针），只用一个 parent 数组就能表示整个森林：

下标 i:   0   1   2   3   4
parent:  [0,  0,  1,  2,  4]

含义：parent[i] 是 i 的父节点。从任意节点沿 parent 往上走，最终会停在一个 parent[x] === x 的节点——那就是根。上例中：

  • 0 的父是 0（自指 → 0 是根）
  • 1 的父是 0（→ 根是 0）
  • 2 的父是 1 → 1 的父是 0（→ 根是 0）
  • 3 的父是 2 → 2 → 1 → 0（→ 根是 0）
  • 4 的父是 4（自指 → 4 是根）

所以这个森林有两个集合：{0,1,2,3}（代表元 0）和 {4}（代表元 4）。

根的标志：parent[root] === root——这是并查集一切逻辑的起点。

初始化 ​

开始时，每个元素自成一组（自己是自己的根）：

js
function init(n) {
  const parent = new Array(n);
  for (let i = 0; i < n; i++) parent[i] = i; // 每个元素自成一组
  return parent;
}

初始化后是 n 个独立集合，每个集合只有一个元素。

三、find：找代表元（根） ​

find(x) 沿 parent 数组一直往上走，直到找到根：

js
function find(parent, x) {
  while (parent[x] !== x) {   // 还没到根
    x = parent[x];             // 往上走一步
  }
  return x;                    // 返回根
}

或递归写法（更简洁，也是路径压缩的基础）：

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

find 返回的就是 x 所属集合的代表元。两个元素 find 结果相同 ⇔ 同一集合。

四、union：合并两个集合 ​

union(x, y) 把 x 和 y 所在的两个集合合并：

js
function union(parent, x, y) {
  const rootX = find(parent, x);   // 找 x 的根
  const rootY = find(parent, y);   // 找 y 的根
  if (rootX === rootY) return;     // 已同组，无需合并
  parent[rootX] = rootY;           // 把 rootX 挂到 rootY 下
}

关键：union 前必须先 find 两个根。直接 parent[x] = y 是错的——那样只把 x 一个节点挪走，x 原来的整棵子树（其它以 x 为根的元素）不会被一起带走。正确做法是把根挂到根下，这样整棵子树都跟着走。

合并后，原来两个集合共享同一个根（代表元），从此 find 任意元素都会落到同一个根。

五、为什么 union 前要先 find 两个根 ​

这是新手最易踩的坑。错误写法：

js
// ❌ 错误：只挪了 x 一个节点，没挪 x 的整棵子树
function wrongUnion(parent, x, y) {
  parent[x] = y;
}

假设森林是 {0,1,2}（2→1→0，根是 0）和 {3}（根是 3）。若执行 wrongUnion(parent, 2, 3)，得到 parent[2] = 3，此时森林变成：0←1（根 0）、2→3（根 3）。元素 2 从集合 {0,1,2} 里「掉队」了，但 1 还在原来的集合——这破坏了「同集合元素根相同」的不变量。

正确做法是把整棵树的根挂到另一棵树的根下：

js
// ✅ 正确：find 找根，根挂根，整棵子树一起走
const rootX = find(parent, x);
const rootY = find(parent, y);
if (rootX !== rootY) parent[rootX] = rootY;

这样 parent[rootX] = rootY 后，原本以 rootX 为根的所有元素，find 时都会顺着新的链接走到 rootY——整棵子树正确迁移。

六、连通性问题：并查集的典型应用 ​

并查集最适合「动态地维护连通关系并查询是否连通」的问题。经典模板——无向图的连通分量个数：

js
function countComponents(n, edges) {
  const parent = init(n);
  let count = n;                    // 初始 n 个独立集合
  for (const [u, v] of edges) {
    const ru = find(parent, u), rv = find(parent, v);
    if (ru !== rv) {                // 不同集合才合并
      parent[ru] = rv;
      count--;                       // 合并一次，集合数 -1
    }
  }
  return count;                     // 剩下的集合数 = 连通分量数
}

逻辑：每合并一次，连通分量数减一；处理完所有边后剩下的集合数就是答案。这类「边加边查、判连通」的场景，并查集几乎是唯一最优解（BFS/DFS 也能做连通分量，但并查集更适合「动态加边」）。

下一步 ​

理解了并查集的基本模型后，下一步是让它「快起来」——朴素实现的树可能退化成链导致 O(n)，而路径压缩 + 按秩合并两大优化能把每次操作压到近乎 O(1)，见路径压缩与按秩合并。