Union-Find（素集合データ構造）の償却計算量

Union-Find が解く問題

Union-Find（素集合データ構造, disjoint-set）は、互いに素な集合の集まりを管理し、次の2操作を高速に処理するデータ構造です。

• find(x) … 要素 x が属する集合の代表元を返す。
• union(x, y) … x の集合と y の集合を1つに併合する。

「2つの要素が同じグループか」は find(x) == find(y) で判定できます。これは動的連結性（要素を足したり辺をつないだりしながら、その都度つながっているか問う）という問題の核心で、ナイーブにグラフ探索でやると毎回 O(n) かかるところを、ほぼ定数時間に縮めます。各操作の速さを表す記法は計算量（Big-O）を前提に進めます。

森による表現

各集合を1本の木で表し、全体を森として持ちます。各要素は親へのポインタ parent[x] だけを持ち、根（parent[x] == x の要素）がその集合の代表元です。配列1本で実装できる軽量なデータ構造です。

集合 {0,1,2} と {3,4} の森の例

    0          3
   / \         |
  1   2        4

parent = [0, 0, 0, 3, 3]   # 0と3が根（代表元）

find(x) は親をたどって根に着くまで上る。union(x, y) は片方の根を、もう片方の根の子にぶら下げるだけです。

function find(x):
    while parent[x] != x:
        x = parent[x]
    return x

function union(x, y):
    rx, ry = find(x), find(y)
    if rx != ry:
        parent[rx] = ry   # 素朴版：単純に片方をぶら下げる

この素朴版には弱点があります。併合の向きを考えないと木が一直線に伸び、find が O(n) に劣化する点です。平衡木が偏りで O(n) 化するのと同じ構図で、ここを2つの最適化で潰します。

最適化1 ― ランク（または size）併合

併合のとき、低い木を高い木の下にぶら下げると木の高さが伸びにくくなります。各根に「木のおおよその高さ」を表すランク（rank）を持たせ、ランクの小さい方を大きい方の子にします。

function union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry: return
    if rank[rx] < rank[ry]:
        parent[rx] = ry
    elif rank[rx] > rank[ry]:
        parent[ry] = rx
    else:
        parent[ry] = rx
        rank[rx] += 1        # 同ランクのときだけ高さが1増える

ランクの代わりに部分木のサイズ（要素数）を使い、小さい木を大きい木にぶら下げる「union by size」でも同等の効果が得られます。どちらも高さ差を意識した併合（union by rank / size）で、これ単体でも木の高さを O(log n) に抑えられます。

最適化2 ― 経路圧縮

もう1つが経路圧縮（path compression）です。find(x) で根まで上る途中に通った全ノードを、直接根の子に付け替えてしまう。次回以降、同じ経路は1ステップで根に着きます。

function find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # 帰りがけに根へ付け替える
    return parent[x]

これは再帰の帰りがけ処理で書くと簡潔です。1回の find で経路上のノードが軒並み平たくなるため、木は使うほどに浅くなっていきます。経路圧縮だけでも、find の償却計算量を O(log n) 水準に抑えられます（素朴版の最悪 O(n) からの大幅な改善です）。

償却 O(α(n)) はなぜ成り立つか

ランク併合と経路圧縮を両方使うと、m 回の操作の総計算量が O(m α(n)) になることが証明されています（Tarjan, 1975）。1操作あたりに均すと O(α(n))、すなわち償却計算量が逆アッカーマン関数です。

ここで「償却」とは、個々の操作ではなく操作列全体で均した1操作あたりのコストを指します。経路圧縮を伴う find は1回が高くつくこともありますが、その分木を平たくして以後の操作を安くするので、列全体で均せば安い、という見方です。

直観は次の通りです。ランク併合により、ランク r の根は最低でも 2 の r 乗個の要素を含むので、ランクは最大でも log n 程度までしか上がりません。さらに経路圧縮が各ノードの親をランクのずっと高いノードへ繰り返し付け替えるため、ノードは「ランクの急成長」を何度も経験できません。この回数を厳密に数えると、アッカーマン関数の逆数が現れます。

なお、ランク併合だけ・経路圧縮だけのどちらか一方では O(α(n)) は出ず、両方が揃って初めてこの限界に到達します。これは Union-Find が「2つの簡単な工夫の組み合わせで、単独の和より良くなる」希少な例です。

応用 ― 動的連結性を問う問題

Union-Find が真価を発揮するのは「つながっているか」を動的に問う場面です。

代表例がKruskal法です。最小全域木（すべての頂点を最小コストでつなぐ木）を求めるとき、辺を重みの軽い順に見て、その辺の両端が別々の集合なら木に採用して union、同じ集合ならスキップします。「同じ集合か」の判定がまさに find で、ここを Union-Find が O(α(n)) で捌くため、Kruskal法全体の支配項は辺のソート O(E log E) になります。

Kruskal法の骨子
辺を重み昇順にソート
for each (u, v, w) in sorted edges:
    if find(u) != find(v):      # 別集合なら閉路にならない
        最小全域木に (u,v) を追加
        union(u, v)

まとめ

Union-Find の本質は、集合を森で表し、代表元（根）を集合IDとして find と union を回す点にあります。素朴な実装は木が偏って O(n) に劣化しますが、ランク併合で高さを抑え、経路圧縮で木を使うたび平たくする、この2つを併用すると m 操作の総計算量が O(m α(n)) に収まります。逆アッカーマン関数 α(n) は現実的な n で 4 以下、すなわち事実上の定数です。Kruskal法の閉路検出、連結成分の数え上げ、画像ラベリングなど、動的連結性を問う問題ではこの「ほぼ O(1) で併合と判定」という性質が決定打になります。配列1本で書ける軽さと理論限界に近い速さを両立する、アルゴリズムとデータ構造の交差点にある名作です。