Union-find：2 行の最適化で 1 回の操作がほぼ定数になる

Union-find が答える問いは 1 つです。要素が次々とまとめられていくとき、その 2 つが同じ組にいるかをいつでも答えられるか。30 行で書けますが、正しい 2 行の最適化を入れて初めて O(alpha(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 の 2 つ目の while が経路圧縮です。x から根までの経路を根に直接つなぎ直すので、次の照会は 1 手で済みます。union の if (this.size[x] < this.size[y]) がサイズによる併合です。小さい木を大きい木の下に付けるので、片側だけ伸びる鎖になりません。

なぜ両方要るのか

最適化	単独での計算量
なし	最悪 O(n)／回（連結リストに退化）
経路圧縮のみ	償却 O(log n)
サイズ併合のみ	O(log n)、圧縮はされない
両方	O(alpha(n))、逆アッカーマンで実用上 4 以下

逆アッカーマン関数は宇宙規模の入力でも 5 未満です。ほぼ定数とはそういう意味で、実際に扱う入力では定数です。

使われる場面

教科書の Kruskal 以外にも、無向グラフの連結成分の数を数える、画像処理で同種の隣接画素を領域にまとめる、コンパイラの型の同値類、辺が動的に追加されるネットワークで 2 点がつながっているかを答える、といった用途があります。

踏んだ 3 つの罠

• 再帰実装はスタックを食い尽くす：再帰の経路圧縮は美しいのですが、100 万ノードの鎖でスタックオーバーフローします。上の 2 段の反復版を使います。
• 圧縮すると rank は正確でなくなる：ランク併合だと、木が低くなったのに記録が高いままになります。size の方が正直で安全です。
• 圧縮されるのは 1 本の経路だけ：union の 2 回の find は a と b から根までを圧縮しますが、途中の節点は次に照会されたときに圧縮されます。これは正常で、部分木を手で走査する必要はありません。

Union-find の価値は行数ではなく、2 つの while を書く気になるかどうかにあります。