ユニオンファインドとは？
ユニオンファインド(Union-Find)、別名 素集合(Disjoint Set)は、各要素がどのグループに属するかを管理し、2つのグループを統合したり、2要素が同じグループかを素早く答える構造です。グラフの連結判定、クラスカルMST、サイクル検出、ネットワークのまとめに使われます。
核心の一行: 「各グループを代表(ルート)1つで識別する」。 2要素の代表が同じなら同じグループです。
2つの操作
- •find(x): xが属するグループの代表(ルート)を返します。親を辿って上へ上がるとルートに着きます。
- •union(a, b): 両方の代表を見つけ、一方を他方の下にぶら下げてグループを統合します。
各要素は parent[] 配列で自分の親を指し、親が自分自身ならそれがルートです。
核心は2つの最適化
素朴に実装すると木が一列に長くなりfindがO(n)になります。2つの最適化でほぼO(1)にします。
- •経路圧縮(path compression): findの途中で通ったノードを直接ルートにつなぎ、次のfindが即座に終わるようにします。
- •ランク/サイズ統合(union by rank/size): 常に小さい(低い)木を大きい木の下に付け、高さが伸びないようにします。
両方を併用すると1操作の平均コストは逆アッカーマン関数α(n)に比例 — 事実上定数です。
動作原理
ステップ1. 初期化: parent[i] = i(全員が自分自身を代表とする1人グループ)。
ステップ2. find(x): parent[x] != x の間は上へ上がりルートを見つけ、経路上のノードを直接ルートにつなぎます。
ステップ3. union(a, b): ra = find(a)、rb = find(b)。異なればランクの小さい方を大きい方の下に付けます(等しければ統合側のランク+1)。
ステップ4. 同グループの問い: find(a) == find(b) なら同じ集合です。
AlgoNoteの可視化は、findがルートを探す経路と、経路圧縮で木が平らになる様子をステップごとに示します。
時間計算量と空間計算量
| 操作 | 計算量 |
|---|---|
| find / union | O(α(n)) ≈ O(1) |
| 空間 | O(n) |
α(n)は逆アッカーマン関数で、現実的な入力では4以下の定数のように振る舞います。
例で追ってみる
要素 {0, 1, 2, 3} がそれぞれ別々にあるとします。
- •union(0, 1) → 0と1が1グループ
- •union(2, 3) → 2と3が1グループ
- •union(1, 2) → 2グループが統合され
{0,1,2,3}1つに - •find(0) == find(3)? → はい(全員同じ代表)
よくあるミス
- •最適化の欠落: 経路圧縮とランク統合のどちらかでも抜けると木が線形に長くなり得ます。
- •代表比較の欠落:
parent[a] == parent[b]で比較してはいけません — 必ずfindでルートを求めて比較します。 - •初期化:
parent[i] = iで始めないとルート判定が壊れます。
AlgoNoteで直接確認しましょう
要素がどうグループに統合され、findがルートを探し、経路圧縮で木が平らになるかをAlgoNoteでステップごとに確認できます。