Union-Find（素集合データ構造）

Union-Find は互いに重ならない集合を維持し、「二要素はすでにつながっているか」を繰り返し答えます。union(a, b) は所属集合を統合し、find(x) は代表元を返します。二つの find が同じなら同じ集合です。ランクによる併合と経路圧縮を合わせると、操作当たり償却 O(α(n)) で、実用上は定数に近い時間です。

Kruskal の最小全域木は、端点が別集合の時だけ辺を加え、閉路を防ぎます。無向グラフの閉路検出、連結成分数、浸透モデル、接続を追加するネットワークにも使います。

parent[i] は i の親です。parent[i] == i なら根であり代表元です。各集合が木、全体が森になります。find は親をたどって根を探し、最適化は経路を短く保ちます。

ランクと経路圧縮

find(x) は parent[x] を読んで移り、自分を指すノードで止まります。

union(a, b) は両方を find します。同じ根なら統合不要、別なら一方の根をもう一方へ向けます。

素朴な実装は常に parent[find(a)] = find(b) とします。union(0,1)、union(1,2)、union(2,3) を続けると一段ずつ鎖が伸び、後の検索は最悪 O(n) です。

二つの最適化で形を制御します。

• ランクによる併合：根に高さの上界 rank を保存します。低ランクを高ランクの下へ付け、異なるランクなら増やしません。同ランクなら勝者を一つ増やします。ランク h には少なくとも 2ʰ 要素が必要で、これだけでも高さ O(log n)。圧縮後のランクは実際の高さと一致する必要はありません。
• 経路圧縮：find で根に着いたら、訪問経路の各ノードを根へ直接向けます。最初の走査が後の検索を短くします。その後の併合で根の関係が変わらなければ、圧縮したノードは次回一跳躍です。

組み合わせた償却界は O(α(n))。α は逆アッカーマン関数で、実用的な入力規模では 5 未満です。極めて遅く増えますが、理論上の定数ではありません。

操作をステップで追う

既定は Optimized、0 から 5 の六要素が別集合です。parent[] は自分を指します。union(0,1)、union(2,3)、union(4,5)、union(0,2)、union(0,4)、その後 find(5) 二回を実行します。

1. union(0,1)：両根はランク 0。同点なら最初の根が勝ち、parent[1] を 1 から 0 へ、0 のランクを 1 へ。
2. union(2,3)、union(4,5) も同じ。根 0、2、4 の二ノード木が三つでき、各ランクは 1。
3. union(0,2)：同ランクなので 2 を 0 の下へ付け、0 はランク 2。0 の直接の子は 1 と 2、2 の下に 3 が残り、3 の深さは 2。
4. union(0,4)：ランク 2 と 1。4 を 0 の下へ付け、ランクは増やさない。全要素が根 0 に属し、3 と 5 は深さ 2。
5. 最初の find(5)：parent[5] = 4、parent[4] = 0 と進み、0 が自己参照する根と分かる。parent[5] を 4 から 0 へ変更。画面の辺と配列が同時に変わり、5 は根の直接の子になる。
6. 二回目の find(5)：一跳躍で 0。これ以上の圧縮はなく、同じ検索の経路が短くなったと分かる。

Naive へ切り替え、union(0,1)、union(1,2) などを連鎖させて find(0) を実行してください。木は段ごとに高くなり、圧縮なしで全高を歩きます。

時間・空間計算量

保存は parent 配列、最適化版には rank もあり、ノードごとのオブジェクトや子ポインターは不要です。ランクだけなら O(log n)。圧縮だけでも訪問経路は短くなりますが、組み合わせた逆アッカーマン界をそのまま主張できません。

サイズによる併合も使えます。要素数を保存し、小集合を大集合の下へ付けます。経路圧縮との組み合わせで同じ漸近界になります。一つの方針を一貫して維持してください。

境界ケース

• すでに連結している二要素：同根なので集合を統合しない。最適化版は早期 return、素朴版は無害な自己代入。find 自体は経路を圧縮することがある。
• 根の find：零跳躍で終了し、圧縮不要。
• 根の直接の子：一跳躍で、リンクはすでに最短。
• union(a, a)：同根の場合。
• 未操作の単独要素：独立集合のまま。異なる二集合を統合した時だけ集合数が減る。

よくある間違い

• parent[a] と parent[b] を比較する。 同集合でも親は違えます。find(a) と find(b) で根を比べます。
• 高ランクを低ランクの下へ付ける。 余分な高さを作り、方針を逆転させます。
• union のたびにランクを増やす。 異なる同ランクの根を併合した時だけ、勝者を一つ増やします。
• 圧縮後のランクを実際の高さとする。 圧縮は高さを下げてもランクを下げません。有効な上界のままでよく、再走査で高さを計算し直す必要はありません。
• 辺の削除や集合分割に使う。 通常の Union-Find は併合だけです。削除には別構造か、適用可能な問題でのオフライン逆順処理が必要です。