并查集：两行优化让每次操作几乎变成常数

并查集处理的问题只有一个：一堆元素不断被合并成组，随时要回答「这两个在不在同一组」。它简单到 30 行就能写完，但只有加了对的两行优化才是 O(α(n))。

实现

class Dsu {
  parent: number[];
  size: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
  }

  find(x: number): number {
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root];
    while (this.parent[x] !== root) {
      const next = this.parent[x];
      this.parent[x] = root;
      x = next;
    }
    return root;
  }

  union(a: number, b: number): boolean {
    let x = this.find(a);
    let y = this.find(b);
    if (x === y) return false;
    if (this.size[x] < this.size[y]) [x, y] = [y, x];
    this.parent[y] = x;
    this.size[x] += this.size[y];
    return true;
  }
}

find 里的第二个 while 是路径压缩：把从 x 到根的整条路径直接挂到根上，下次查就一步到位。union 里的 if (this.size[x] < this.size[y]) 是按大小合并：小树挂到大树上，树高才不会被单侧拉长。

为什么两个都要

优化	单独使用的复杂度
无	最坏 O(n) 每次（退化成链表）
只用路径压缩	摊还 O(log n)
只用按大小合并	O(log n)，且压缩不到
两者都用	O(α(n))，反阿克曼，实际 ≤ 4

反阿克曼函数在宇宙尺度上都小于 5 —— 也就是说理论上的「几乎常数」在实际输入范围内就是常数。

用在什么地方

除了教科书里的 Kruskal 最小生成树，它还有几个实用场景：判断一张无向图有几个连通分量、图片处理里把相邻的同类像素合并成区域、编译器的类型等价类、以及网络里动态加入连接后回答「这两个点通不通」。

三个踩过的坑

• 递归实现会爆栈：路径压缩写成递归很优雅，但在 10^6 个节点的链上直接栈溢出。用上面那种两趟迭代版。
• 压缩之后 rank 不再准确：如果用的是「按秩合并」，压缩会让记录的秩偏高（树已经变矮了）。用 size 更稳，语义也不会失真。
• 只压缩一条路径：union 里两次 find 各自压缩了从 a 与 b 到根的路径，但中间节点的路径要等以后查询时才被压。这是正常的，不用在 union 里手动遍历整棵子树。

并查集的价值不在代码量，而在你愿意为它写两个 while。