実装で用いる Int32Array の仕様は MDN Web Docs を参照しました。本文の設計、コード、例は新規に書き下ろしたものです。

TypeScriptでUnion-Findを実装する：経路圧縮・サイズ併合・不変条件をテストで確かめる

「2人は同じグループに属するか」を何度も問い合わせ、途中でグループを結合していく問題では、Union-Find（Disjoint Set Union, DSU）が有効です。面接では単に実装を暗記するより、なぜほぼ定数時間になるかと配列の不変条件を説明できると強くなります。

この記事では、再帰を使わない TypeScript 実装を作り、結合・問い合わせ・グループ数・サイズを一つの配列で扱います。

先に結論

• parent[i] < 0 なら i は根で、値の絶対値は集合サイズです。
• parent[i] >= 0 なら、その値は親ノードの添字です。
• find で経路圧縮、union でサイズ併合を行うと、1操作の償却計算量は O(α(n)) になります。実用上はほぼ定数時間です。
• 「根だけが負のサイズを持つ」という不変条件を守れば、sizeOf と components を追加コストなしで実装できます。

どんな問題に使うか

例えば、ユーザーIDを頂点、相互接続を辺として扱う場合を考えます。

• 接続要求を受けたら union(a, b)
• 同じネットワークかを調べるなら connected(a, b)
• 孤立したグループを数えるなら components

辺を追加するだけで、途中で辺を削除しない問題に特に向いています。島の個数、アカウント統合、冗長な接続の検出も同じ形に落とせます。

配列の不変条件

初期状態では全ノードが1要素の集合です。要素数が7なら内部配列は次のようになります。

index :  0  1  2  3  4  5  6
parent: -1 -1 -1 -1 -1 -1 -1

union(0, 1) の後、根を 0 と決めると parent[0] = -2、parent[1] = 0 です。

index :  0  1  2  3  4  5  6
parent: -2  0 -1 -1 -1 -1 -1

負の値を「親なし」と「サイズ」の両方に使えるため、size 配列を別に持つ必要がありません。この表現で重要なのは、根以外に負の値を置かないことです。

実装：反復版 find とサイズ併合

再帰版の find は短く書けますが、JavaScript では極端に深い木でコールスタックを使います。ここでは根まで登る1回目のループと、通ったノードを根へ付け替える2回目のループに分けます。

class UnionFind {
  #parent: Int32Array;
  components: number;

  constructor(n: number) {
    if (!Number.isInteger(n) || n < 0) {
      throw new RangeError("n must be a non-negative integer");
    }
    this.#parent = new Int32Array(n);
    this.#parent.fill(-1);
    this.components = n;
  }

  #assertIndex(x: number) {
    if (!Number.isInteger(x) || x < 0 || x >= this.#parent.length) {
      throw new RangeError("index out of range: " + x);
    }
  }

  find(x: number): number {
    this.#assertIndex(x);

    let root = x;
    while (this.#parent[root] >= 0) {
      root = this.#parent[root];
    }

    while (x !== root) {
      const next = this.#parent[x];
      this.#parent[x] = root;
      x = next;
    }

    return root;
  }

  union(a: number, b: number): boolean {
    let rootA = this.find(a);
    let rootB = this.find(b);

    if (rootA === rootB) return false;

    // 負の値では、絶対値が大きいほど集合も大きい
    if (this.#parent[rootA] > this.#parent[rootB]) {
      [rootA, rootB] = [rootB, rootA];
    }

    this.#parent[rootA] += this.#parent[rootB];
    this.#parent[rootB] = rootA;
    this.components--;

    return true;
  }

  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }

  sizeOf(x: number): number {
    return -this.#parent[this.find(x)];
  }
}

なぜ比較が > なのか

根の値はサイズの負数です。サイズ3は -3、サイズ2は -2 なので、-2 > -3 です。したがって parent[rootA] > parent[rootB] のときは、Aの木の方が小さく、AをBの下に接続します。

この規則がないと、結合順によって細長い木ができやすくなります。サイズ併合だけでも木の高さを抑えられ、さらに find の経路圧縮が後続の探索を短縮します。

動作を固定するテスト

テストでは「同じ集合への再結合は false」「サイズとグループ数が正しい」「範囲外の添字を拒否する」を確認します。Bun では次のまま実行できます。

import { strict as assert } from "node:assert";

// UnionFind クラスは上の実装を利用する
const uf = new UnionFind(7);

assert.equal(uf.components, 7);
assert.equal(uf.union(0, 1), true);
assert.equal(uf.union(1, 2), true);
assert.equal(uf.union(3, 4), true);
assert.equal(uf.union(0, 2), false);

assert.equal(uf.connected(0, 2), true);
assert.equal(uf.connected(0, 3), false);
assert.equal(uf.sizeOf(1), 3);
assert.equal(uf.components, 4);
assert.throws(() => uf.find(7), RangeError);

この例では、union(1, 2) のとき find(1) が根を返し、必要なら親ポインタを根へ圧縮します。呼び出し側は「途中の親」を意識せず、常に find の戻り値だけを根として扱えます。

面接で説明する順番

実装を説明するときは、次の順番にすると意図が伝わります。

1. parent の符号で「根・サイズ」と「親」を区別する。
2. find は根を探し、通過したノードを根に付け替える。
3. union は根同士だけを比べ、小さい集合を大きい集合へ接続する。
4. 同じ根なら状態を変えず false を返す。これがグループ数を正しく保つ。
5. 辺の削除があるなら、この構造だけでは扱えないため別の設計を検討する。

Union-Findは短い実装ですが、不変条件・償却計算量・適用範囲まで説明できると、単なるテンプレート利用ではなく設計判断として示せます。