高级数据结构

并查集

它只做两件事

并查集（Union-Find / 并查集）的接口极小：

  • find(x) —— x 属于哪个集合
  • union(x, y) —— 把两个集合合并

就这两个。它做不了「列出某个集合里的所有元素」「拆分集合」这些事 —— 功能少到极致，换来的是接近 O(1) 的速度。

⭐ 和图遍历比：DFS 也能判连通， 但每问一次就要重新跑一遍 O(V+E)。并查集把状态维护起来， 适合「边不断加进来、随时要问连不连通」的场景。

最朴素的版本

用一棵树表示一个集合，parent[x] 指向父节点，根节点指向自己：

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);   // 各自成一个集合
    this.count = n;                                          // 连通分量个数
  }

  find(x) {
    while (this.parent[x] !== x) x = this.parent[x];         // 一路往上找根
    return x;
  }

  union(x, y) {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;      // 本来就在一个集合里
    this.parent[rx] = ry;
    this.count--;                     // 合并一次，分量数减一
    return true;
  }

  connected(x, y) { return this.find(x) === this.find(y); }
}

🚨 union 里必须先 find 到根再连，不能直接 parent[x] = y。 直接连有两种后果，而且第二种比第一种糟得多：

① 把 x 原来那棵树的其余部分甩掉
   边 [0,1] [2,3] [0,2]   正确分量数 1，直接连得 2
   （0 被从 {0,1} 里拽走，1 掉队）

② 造出环，find 死循环
   边 [0,1] [1,0]          parent[0]=1, parent[1]=0 —— while 循环再也出不来

⚠️ 5000 组随机边序列实测：

find 死循环     19.2%
分量数算错      33.7%
碰巧对          47.1%

🚨 环那一种不报错也不返回，程序直接挂住 —— 比算错更难查。 而将近一半的输入上它碰巧是对的，所以「我跑通了」什么都说明不了。

⚠️ 这个朴素版最坏是 O(n)：按 union(0,1), union(1,2), union(2,3)… 的顺序合并，树会退化成一条链，find 要一路走到底。

n = 3000 实测：这样合并之后，从节点 0 走到根的深度是 2999 —— 一条毫无分叉的链。把所有节点各 find 一遍要 4498500 步。

🚨 注意这取决于 union 里挂哪一边。上面写的是 parent[rx] = ry （x 的根挂到 y 的根下）。反过来写成 parent[ry] = rx 的话， 同样的调用顺序会长成一棵扁平的星形，反而不退化：

同样是 n=3000、同样的 union(i, i+1) 顺序
  parent[rx] = ry     最大深度 2999    全部 find 一遍 4498500 步
  parent[ry] = rx     最大深度    1    全部 find 一遍      2999 步     1500×

⭐ 一个方向之差，同一份数据上性能差 1500 倍。 朴素并查集的最坏情况是可以被输入顺序「碰巧躲开」的， 所以别用「我测了没问题」当作不需要优化的理由。

两个优化

① 路径压缩：找过一次就把路捋直

find(x) {
  if (this.parent[x] !== x) {
    this.parent[x] = this.find(this.parent[x]);   // 顺手把 x 直接挂到根上
  }
  return this.parent[x];
}

⭐ 一行递归。它在返回的路上，把整条路径上的所有节点都直接指向根 —— 下次再 find 这条路上任何一个点，都是一步到位。

接着上面那个退化成链的例子（n = 3000）实测：

把所有节点各 find 一遍
  无路径压缩：4498500 步
  有路径压缩：   5997 步        ← 750 倍

⚠️ 注意这 5997 步是第一遍的开销（压缩本身要走一次）， 而且它恰好是 2n - 3：一次 2999 步走到根，其余 2998 个点各 1 步。

之后再怎么 find 都是常数步 —— 第二遍实测只要 2999 步， 即每个非根节点恰好 1 步。压缩的收益随查询次数增加而放大。

② 按秩合并：让矮树挂到高树下面

union(x, y) {
  const rx = this.find(x), ry = this.find(y);
  if (rx === ry) return false;
  // 🚨 小的挂到大的下面，否则树会越长越高
  if (this.size[rx] < this.size[ry]) { this.parent[rx] = ry; this.size[ry] += this.size[rx]; }
  else                               { this.parent[ry] = rx; this.size[rx] += this.size[ry]; }
  this.count--;
  return true;
}

⭐ 两个优化一起用，单次操作的均摊复杂度是 O(α(n)) —— α 是反阿克曼函数，在任何现实规模下都小于 5。实践中可以当常数。

这句话可以直接量：随机合并之后，量出整棵森林里最深的那条路径有多长。

n =     1,000     最大树深 3
n =   100,000     最大树深 3
n = 1,000,000     最大树深 3

⭐ 规模涨一千倍，最深路径一动不动。这就是「可以当常数」的实际含义。

📌 面试里只写路径压缩通常就够（它单独就能把复杂度压到 O(log n) 级别）， 但能说出「还有按秩合并，两个一起是 α(n)」是加分项。

⚠️ 一个真实的陷阱：路径压缩会破坏「秩」

按秩合并里的 size 或 rank，在路径压缩之后不再准确 —— 压缩把树压扁了，但 size 没跟着更新。

🚨 这不是 bug，不用修。size 在这里只是一个「启发式」， 用来决定哪边挂哪边，不精确也不影响正确性，只是让复杂度分析变复杂。 真去维护精确值反而会拖慢。

📌 但要知道这回事 —— 面试被问「压缩之后 rank 还准吗」， 答「不准，但它只是启发式，不影响正确性」。

典型应用

连通分量计数 —— count 字段直接就是答案，不用另外算。

判断加边会不会成环 —— union 返回 false 就说明两点本来就连通， 这条边会形成环。Kruskal 求最小生成树全靠这一条：

function kruskal(n, edges) {
  edges.sort((a, b) => a[2] - b[2]);      // 按权重从小到大
  const uf = new UnionFind(n);
  let total = 0, used = 0;
  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) { total += w; used++; }   // 不成环才要这条边
    if (used === n - 1) break;                    // 树有 n-1 条边
  }
  return used === n - 1 ? total : -1;             // 连不起来说明图不连通
}

等式方程的可满足性 —— a==b 的先全部 union 起来， 再检查每个 a!=b 是否落在同一个集合里。

⭐ 这题的关键是顺序：必须先处理所有等式，再处理所有不等式。 反过来的话，后来的等式可能会推翻之前已经通过的不等式检查。最小反例只要两条：

["a!=b", "b==a"]
  先等式后不等式  → false   ✅ 正确（a==b 与 a!=b 矛盾）
  混着一遍扫过去  → true    ❌ 扫到 a!=b 时 a 和 b 还没被 union

⚠️ 注意把这两条换个次序（["a==b","b!=a"]）两种写法就都对了 —— 所以这个 bug 只在「不等式出现在等式之前」时才暴露，而用例往往是等式在前。

并查集 vs DFS，怎么选

并查集 DFS/BFS
边动态加入 ⭐ 强项 每次都要重跑
只问连通性 ⭐ 强项 能做但浪费
要具体路径 ❌ 做不到 ⭐ 强项
要遍历某个分量的所有点 ❌ 做不到 ⭐ 强项
有向图 ❌ 不适用 ⭐ 适用

🚨 最后一行值得强调：并查集只处理无向的连通性。 「a 能到 b」这种有向可达性它答不了 —— 它只知道「a 和 b 在同一堆里」。

本章到此为止

高级数据结构五篇齐了。回头看，它们各自用一种「约束」换一种「速度」：

  • BST —— 全序，换来有序遍历与范围查询
  • 堆 —— 只管父子，换来 O(1) 取最值
  • 树状数组 / 线段树 —— 放弃 O(1) 查询，换来修改也是 O(log n)
  • 字典树 —— 合并公共前缀，换来与词典规模无关的前缀查询
  • 图 —— 放弃「无环」，换来表达任意关系
  • 并查集 —— 只留 find/union 两个操作，换来近乎 O(1)

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。