素集合データ構造

素集合データ構造
種類	多分木
発表時期	1964年
発明者	バーナード・ガラー、マイケル・フィッシャー
ビッグオー記法による計算量 (en)

素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いに重なりを持たない集合）に分割して保持するデータ構造である。Union-Findデータ構造（union–find data structure）、Merge-Find集合（merge–find set）とも呼ばれる。数学的には、集合の分割を保持するデータ構造と言い換えることができる。

このデータ構造は、次の3つの操作を提供する。

MakeSet: 与えられた1つの要素だけを格納した集合（シングルトン）を新しく作る。
Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
Union: 2つの集合を1つに統合する。

このうち Find と Union の2つの操作に着目したものはUnion-Findアルゴリズムとも呼ばれる。これらの操作により、無向グラフの連結成分の管理など、様々な実用的な分割問題を解くことができる（「応用」の節を参照）。

実装方法はいくつかあるが、実際には素集合森（disjoint-set forest）と呼ばれる木の森を使った実装を指すことが多い。素集合森では、後述する工夫を組み合わせることで、n 個の要素に対する m 回の操作の合計時間が O(m α(n)) となる。ここで α(n) は極めてゆっくりと増加するアッカーマン関数の逆関数であり、実用上は定数とみなせる^[1]^[2]。この計算量は漸近最良であることが知られている^[3]。

素集合データ構造は、グラフの最小全域木を求めるクラスカル法の実装に欠かせないデータ構造である。

定義

有限集合 S が、互いに素な部分集合（クラス）X₀, X₁, …, X_k に分割されているとする。

S=X_{0}\uplus X_{1}\uplus \cdots \uplus X_{k},\quad X_{i}\cap X_{j}=\varnothing \ (i\neq j)

それぞれのクラス X_i から固定の要素を1つ選び、その集合全体を表す代表（representative、代表元、正準元）とする。素集合データ構造は、この代表を介して次の操作を効率的に実行する^[4]。

MakeSet(x): x のみを要素とする新しいクラス {x} を作り、x をその代表とする。
Find(x): x が属するクラスの代表を返す。2つの要素 x, y が同じクラスに属する必要十分条件は Find(x) = Find(y) である。
Union(x, y): x が属するクラスと y が属するクラスを統合し、1つのクラスにする。統合後の代表は実装によって決まる（呼び出し側が指定できる定義もある）。

素集合データ構造では Union による統合のみを扱い、1つのクラスを2つに分割する操作は基本的に提供しない。分割を扱う別のデータ構造として分割の精密化（英語版）がある。

素集合連結リスト

素集合データ構造を生成する単純な手法としては、集合毎に連結リストを生成する方法がある。リストの先頭の要素がその集合の代表となる。

MakeSetは1要素のリストを生成する。Unionは2つのリストを連結する操作で、定数時間の操作である。この実装の欠点は、FindがΩ(n)または線形時間を必要とする点である。

これを防ぐには、連結リストの各ノードにそのリストの先頭へのポインタを格納しておけばよい。つまり、Findの引数がノードへのポインタであれば、即座にそのノードが属するリストの先頭（代表）がわかる。しかし、このように実装すると今度はUnion操作で各ノードの先頭へのポインタを更新しなければならなくなり、Ω(n) の時間がかかるようになる。

各リストの長さがわかっているなら、短い方を長い方に連結することでUnionの性能を改善できる。これ (weighted-union heuristic) を採用すると、n個の要素について、m回のMakeSet、Union、Find操作を行ったときにかかる時間は O(m + nlog n) となる^[5]。漸近的により高速な操作には別のデータ構造が必要である。

解析

上記の O(nlog n) は次のように導かれる。各ノードが自分の属するリストの先頭へのポインタを持ち、短い方のリストを長い方に連結するものとする。

ある要素 x に注目すると、x のポインタが書き換えられるのは、x が属するリストが、自分と同じかそれ以上の長さのリストに連結されるときに限られる。このとき、x が属するリストの長さは少なくとも2倍になる。リストの長さは最大でも n なので、1つの要素のポインタが書き換えられる回数は多くても log₂ n 回である。したがって、全要素の書き換えの総数は O(nlog n) となる。同様の議論は、後述する素集合森の併合や、二項ヒープ・フィボナッチヒープの解析にも現れる。

また、各ノードが先頭へのポインタを持つので、この実装での Find は O(1) で行える。

素集合森

素集合森 (disjoint-set forest) はそれぞれの集合を木構造で表したデータ構造で、各ノードには親ノードへの参照がある。1964年、Bernard A. Galler と Michael J. Fischer が考案したが^[6]、詳細な解析にはその後何年かかかった。この表現は考案者にちなんでGaller-Fischer木とも呼ばれる。

表現

素集合森では、各集合の代表は木構造の根となる。各ノードは親ノードへのポインタを1つだけ持つ。根は自分自身を親として指すことで区別するのが一般的である（null ポインタなどの番兵を使う方法もある）。2つのノードが同じ集合に属する必要十分条件は、両者が属する木の根が同じことである。

アルゴリズムによっては、根のノードに木のサイズ（要素数）かランク（後述）のいずれかを補助情報として持たせる。これらは根でのみ必要なので、親ポインタを格納する領域にタグ付きポインタ（英語版）として同居させることもできる。また、ノードを配列に格納して親を添字で表す実装もよく使われる。このとき親ポインタ1つあたり log₂ n ビットが必要なので、森全体では Θ(n log n) ビットを要する。^[要出典]

MakeSet

MakeSet は、新しい要素 x の親を x 自身にして、1要素だけの木を作る。サイズやランクを使う場合は同時に初期化する。1回の MakeSet は定数時間であり、n 個の要素で森を初期化するには O(n) の時間がかかる。

 function MakeSet(x)
     x.parent := x
     x.size   := 1  // サイズを使う場合
     x.rank   := 0  // ランクを使う場合

Find

Find は親ノードへのリンクを根に到達するまでたどり、その根を返す。Union は2つの木を1つにする操作であり、どちらかの根が全体の根となる。以下に素朴な素集合森の実装例を擬似コードで示す。

 function MakeSet(x)
     x.parent := x

 function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

この素朴な実装では、連結リストを使った場合と変わらない。なぜなら、木構造の平衡が保たれないからである。例えば要素 1, 2, …, n に対して Union(1, 2), Union(2, 3), …, Union(n−1, n) をこの順に実行すると、根が n で、1 から n までの経路が全ノードを通る1本の鎖ができ、Find(1) に O(n) かかる。しかし、これを改善する方法が2つある。

経路圧縮

path compression（経路圧縮）は、Find操作を行ったときに構造を平坦化する改善である。Findで根ノードまでのリンクをたどっているとき、各ノードは同じ代表を共有しているので、それらを根ノードに直接接続できる。このため、Find は再帰的にたどったノードが全て親ノードとして根ノードを指すように変更する。こうすると木構造はより平坦になり、その後の操作が高速化される。この更新は集合の分割内容を変えないので、安全に行える。以下に Find の改良版を示す。

 function Find(x)
     if x.parent == x
        return x
     else
        x.parent := Find(x.parent)
        return x.parent

この再帰による実装は、根まで上る処理と根から戻る処理の2回の走査を行い、根までの経路を記憶する領域（上の擬似コードではコールスタック）を必要とする。根を探す走査と親を付け替える走査を同じ向きに2回行えば、記憶領域を定数にできる。

 function Find(x)
     root := x
     while root.parent != root
         root := root.parent

     while x.parent != root
         parent := x.parent
         x.parent := root
         x := parent

     return root

経路分割と経路半減

Tarjan と van Leeuwen は、最悪計算量を保ったまま、根に向かう1回の走査だけで済み実用上より効率的な Find のアルゴリズムも考案している^[2]。これは経路分割（path splitting）と経路半減（path halving）と呼ばれ、どちらも経路上のノードの親を根に近いノードに付け替える。

経路分割は、経路上のすべてのノードの親を、そのノードの祖父（親の親）に付け替える。

 function Find(x)
     while x.parent != x
         (x, x.parent) := (x.parent, x.parent.parent)
     return x

経路半減は、経路上の1つおきのノードだけの親を祖父に付け替える。

 function Find(x)
     while x.parent != x
         x.parent := x.parent.parent
         x := x.parent
     return x

経路分割・経路半減は、再帰や経路の記憶を必要とせず、ループ1回で書けるため実装が簡潔である。

Union

MakeSet により8個のシングルトンを作った状態。

いくつかの Union を行った後の状態。いくつかの集合が1つにまとまっている。

Union(x, y) は、まず Find で x と y それぞれの根を求める。根が同じなら何もしない。異なれば、一方の根の親をもう一方の根にして2つの木を連結する。どちらを親にするかは以降の操作の計算量に影響し、無頓着に選ぶと木が高くなりすぎる。木の高さを抑えるため、効率的な実装では union by size か union by rank を用いる。どちらも、根に親ポインタ以外の情報を持たせて、どちらの根を新しい親にするかを決める。

サイズによる併合

union by size（サイズによる併合）では、根が部分木の要素数（自分自身を含む子孫の数）を持ち、Union で要素数が大きい方の木の根を全体の根にする。要素数が等しければどちらでもよい。併合後の根のサイズは、2つのサイズの和に更新する。

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)

     if xRoot == yRoot
         return  // x と y は既に同じ集合に属している

     // xRoot の方が要素数が大きくなるようにする
     if xRoot.size < yRoot.size
         (xRoot, yRoot) := (yRoot, xRoot)

     yRoot.parent := xRoot
     xRoot.size   := xRoot.size + yRoot.size

この方法では、要素が属する木の根までの深さは併合のたびに増えても、そのたびに属する木の要素数が2倍以上になるため、高さが log₂ n を超えない^[4]。

ランクによる併合

union by rank（ランクによる併合）は、Union操作で常に大きい木の方が全体の根になるように連結するものである。木の大きさを評価するにはrank を用いる。これは、1要素の木の rank を 0 とし、同じ rank r の木を連結したとき、全体の根とした方の木の rank を r+1 とするものである。rank は木の高さの上限であるが、高さそのものではない。高さは Find の経路圧縮によって変化するので、高さを正確に保つ代わりに、rank を保持して更新の手間を避けている。このようにするだけで、MakeSet、Union、Find 操作の償却実行時間は $O(\log n)$ となる。改良した MakeSet と Union の擬似コードは以下のようになる。

 function MakeSet(x)
     x.parent := x
     x.rank   := 0

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot != yRoot // x と y が同じ集合にない場合だけマージする。
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

すべてのノードの rank は ⌊log₂ n⌋ 以下であることが示せる^[4]。したがって rank は1要素あたり O(log log n) ビットで保持でき、全体でも O(n log log n) ビットなので、森全体の記憶量に対しては漸近的に無視できる。

サイズも rank も、根以外のノードでは参照されない。ノードが子になった時点で、そのサイズや rank は二度と使われない。

実装

サイズによる併合と経路半減を組み合わせた素集合森の実装例をPythonで示す。要素は 0 から n−1 の整数とし、親を配列で保持する。根は自分自身を親とする。

class DisjointSet:
    """サイズによる併合と経路半減を用いた素集合森。"""

    def __init__(self, n):
        # 根は自分自身を親とする（MakeSetをn回行った状態）
        self.parent = list(range(n))
        self.size = [1] * n
        self.group_count = n

    def find(self, x):
        """xが属する集合の代表（根）を返す。"""
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        """xとyの集合を統合する。統合したときTrueを返す。"""
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return False
        if self.size[x_root] < self.size[y_root]:
            x_root, y_root = y_root, x_root
        self.parent[y_root] = x_root
        self.size[x_root] += self.size[y_root]
        self.group_count -= 1
        return True

    def same(self, x, y):
        """xとyが同じ集合に属するか判定する。"""
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """xが属する集合の要素数を返す。"""
        return self.size[self.find(x)]

使用例を示す。

ds = DisjointSet(5)
ds.union(0, 1)
ds.union(1, 2)
print(ds.same(0, 2))   # True
print(ds.same(0, 3))   # False
print(ds.get_size(2))  # 3
print(ds.group_count)  # 3

計算量

これらの手法は相補的であり、これを共に行うことで各操作の償却実行時間は $O(\alpha (n))$ となる。ここで $\alpha (n)$ は関数 $f(n)=A(n,n)$ の逆であり、 $A$ は非常に高速に大きな値になるアッカーマン関数である。 $\alpha (n)$ はその逆関数なので、実用的な $n$ の値に対しては常に 5 未満（現実に書き表せる $n$ であれば 4 以下）の値になる^[4]。したがって、各操作の償却実行時間は事実上非常に小さな定数となる。

実装の組み合わせごとの計算量を、n 個の要素に対する m 回の操作（うち MakeSet は高々 n 回）について整理すると次のようになる。

実装	計算量
経路圧縮も併合の工夫も行わない	1回の Find・Union が最悪 O(n)
経路圧縮のみ	最悪 Θ(n + f (1 + log_2+f/n n))。ここで f は Find の回数、Union は高々 n−1 回^[4]
ランクによる併合のみ（経路を更新しない）	全体で Θ(m log n)^[4]
サイズ／ランクによる併合 + 経路圧縮・分割・半減	全体で Θ(m α(n)) 、1操作あたり償却 Θ(α(n))^[2]^[7]

この計算量は、素集合データ構造として漸近最良である。Fredman と Saks は1989年、どのような素集合データ構造でも1回の操作あたり平均（償却）で $\Omega (\alpha (n))$ 個の O(log n) ビットの語にアクセスする必要があることを示した^[3]。これより前の1979年に、Tarjan は Galler-Fischer 木を含むポインタアルゴリズム（英語版）の範囲で同じ下界が成り立つことを示している^[7]。なお、Find と Union の両方を償却 O(1) で行う素集合データ構造は存在しない。

O(m log^* n) の証明

α(n) の厳密な解析はやや複雑であるが、償却時間が O(m log^* n) であること（log^* は反復対数）は、より簡単な議論で示せる^[8]^[1]。ランクによる併合と経路圧縮を用いるとして、次の3つの補題が成り立つ。

根に向かって Find が辿るノードの rank は、辿るにつれて真に増加する。（併合では rank の小さい木が大きい木の下に付き、経路圧縮では辿ったノードが、それより rank の大きい根の直下に付くため、この性質は保たれる。）
rank が r のノードを根とする部分木には、少なくとも 2^r 個のノードがある。（rank r+1 になるのは rank r の木同士を併合したときだけだから、帰納的に 2^r + 2^r = 2^r+1 個以上になる。）
rank が r のノードは高々 n/2^r 個である。（補題2より。）

rank を区間 [0], [1], [2, 3], [4, 15], [16, 65535], … のように、区間の上端が前の区間の下端の2のべき乗になるように「バケツ」に分ける。ノードの rank は n 以下なので、バケツの数は高々 log^* n 個であり、rank が [B, 2^B−1] の範囲にあるノードの数は高々 2n/2^B 個である。

Find の総コストを、(1) 根に至るリンクの辿り（1回の Find につき1回）、(2) 異なるバケツのノード間のリンクの辿り、(3) 同じバケツのノード間のリンクの辿り、に分けて数える。(1) は O(m)、(2) は 1回の Find につき高々バケツの数の log^* n 回なので O(m log^* n) である。(3) については、バケツ [B, 2^B−1] に属するノード u が、経路圧縮により同じバケツ内の別の親に付け替えられる回数は、補題1より親の rank が毎回増加するので高々 2^B 回である。バケツ内のノード数は高々 2n/2^B なので、全バケツで合計しても高々 2n log^* n となる。以上から、全体で O(m log^* n) が得られる。

派生と拡張

素集合森の基本形には、用途に応じて様々な変種や拡張が考案されている。

最悪時間の改善

ランクまたはサイズによる併合を用いた木での Find の最悪時間は Θ(log n) である。1985年、Blum は経路圧縮を使わず、Union の際に木を圧縮することで、1操作あたりの最悪時間を O(log n / log log n) とする実装を示した^[9]。これは Galler-Fischer 木に比べて最悪時間は優れるが、償却時間では劣る。1999年に Alstrup らは、最悪時間 O(log n / log log n) を最適に達成しつつ、償却時間も逆アッカーマン関数である構造を示した^[10]。

要素の削除

通常の素集合森は要素の削除に向いていない。要素を削除しても、その分だけ Find が速くなるわけではないからである。しかし、削除を定数時間で行え、Find の時間が現在の要素数に依存する実装も設計されている^[11]^[12]。また、削除に対応した複雑な手法の調査として Galil と Italiano のものがある^[13]。

バックトラック

素集合森の一部の変種はバックトラック、すなわち直前の Union を取り消す操作に対応するよう拡張できる。Union と Find を1操作あたり O(log n / log log n) 時間、直前の Union の取り消し（Backtrack）を O(1) 時間で実行できるデータ構造が知られている。この結果では、Union が統合後の代表を自由に選べることが本質的である。また、分離可能なポインタアルゴリズムの範囲では、これより良い償却時間は達成できない^[14]。

永続化

永続データ構造として、過去のバージョンを保持する素集合データ構造も研究されている。2007年、Sylvain Conchon と Jean-Christophe Filliâtre は半永続（semi-persistent）版の素集合森を発表した（詳細は「歴史」の節を参照）。半永続とは、過去のバージョンを効率的に保持するが、過去のバージョンへアクセスするとそれより新しいバージョンが無効になる、という意味である^[15]。

競技プログラミングなどでは、最新の状態のみ更新でき、過去の任意の時点の状態を参照できる部分永続（partially persistent）な Union-Find も用いられる。これは経路圧縮を行わず、各ノードが「いつ別の木の子になったか」の時刻を記録するもので、時刻 t における根は、記録された時刻が t を超えるノードに達するまで親をたどれば得られる。併合をサイズによって行えば木の高さは O(log n) に抑えられるので、各時点での Find や2要素が同じ集合に属するかの判定は、併合回数を M として O(log M) 程度で行える。各根の併合時刻とサイズの履歴を記録して二分探索すれば、過去の時点の集合のサイズや、2要素がいつ併合されたかも求められる。^[要出典]

特殊な場合の線形時間

可能な併合に制約がある問題に対しては、真に線形時間のアルゴリズムが可能である。Gabow と Tarjan は、集合の全要素を含む木（union tree）があらかじめ与えられていて、併合が v をその親 p[v] と併合する形 Union(v, p[v]) に限られる場合に、線形時間で実行できることを示した^[16]。

集合の付加情報の保持

素集合森の根に、集合全体に関する情報を持たせる拡張が広く使われている。

集合の代表値: 各根に集合の要素の最小値・最大値・総和などの値を持たせ、Union の際に2つの根の値を合成して新しい根に格納する。たとえば各集合の最小要素と最大要素を保持すれば、「ある要素と連続して並ぶ（同じ集合に属する）範囲の左端と右端」を Find 1回分の時間で取得できる。合成に使う演算が結合法則と交換法則を満たす（可換な半群・モノイドである）ならば、一般の演算をこのように載せることができる。^[要出典]
重み付き Union-Find: 各ノードに「親との間の重み（ポテンシャル）の差」を持たせたものを重み付き Union-Findと呼ぶ。経路圧縮の際には、辿った経路上の差を足し合わせて根との差に付け替える。これにより、同じ集合に属する2要素 x, y の間の差が定まるとき、その値を Find と同程度の時間で求められる。また、「y の重みは x の重みより w だけ大きい」という関係を追加する際には、既に分かっている関係との矛盾も検出できる。重みの演算は群であればよい。^[要出典]
要素の列挙: 通常の素集合森では、ある要素と同じ集合に属する要素の列挙に O(n) かかる。各要素に「次の要素」を指す参照を持たせ、1つの集合の要素を循環リストで結んでおく。2つの集合を併合するときは、それぞれの集合から1つずつ要素を選んで、それらの「次の要素」を交換するだけで、2つの循環リストを1つに連結できる。これにより、大きさ k の集合の全要素を O(k) で列挙できる。^[要出典]

応用

素集合データ構造は集合の分割をモデル化したもので、例えば無向グラフの連結成分などに対応する。したがって、2つの頂点が同じ成分に属するかどうかを調べたり、新たな辺を追加することで閉道となるかを調べるのに利用できる。辺を1本ずつ追加しながら、辺の両端が既に同じ集合に属していれば閉路ができたと判定できる。

Boost Graph Library では、Incremental Connected Components 機能の実装に素集合データ構造を使っている。また、グラフの最小全域木を求めるクラスカル法の実装にもこれを使っている。クラスカル法では、辺を重みの小さい順に見ていき、その両端が異なる集合に属する場合に限り辺を採用して2つの集合を併合する。

その他の応用として、次のものが挙げられる。

単一化の高性能な実装に Union-Find が用いられる^[17]。
Hoshen–Kopelman法（英語版）（格子状のデータの連結成分のラベル付け）は Union-Find を使う。
型推論アルゴリズムの実装にも利用できる。^[要出典]
グラフから辺を削除していくクエリは、クエリを逆順に見ると辺の追加に変わるので、オフラインであれば Union-Find で処理できる。^[要出典]

なお、素集合森の実装では削除ができない点に注意されたい。上述した2つの改良を施しても削除は容易ではないが、削除に対応したもっと複雑な手法が既に設計されている（「要素の削除」の節を参照）^[13]。

歴史

素集合森は1964年に Galler と Fischer によって考案され^[6]、考案されてからよく使われていたが、1973年にジョン・ホップクロフトとジェフリー・ウルマンが、操作毎の時間の上限が O(log^* n) であることを証明した^[8]。log^* は反復対数であり、これも増加の遅い関数である（ただし、アッカーマン関数の逆関数ほどではない）。その後、上限（そして限定的な下限）がアッカーマン関数の逆関数であることを証明したのはロバート・タージャンだった。1975年に Tarjan が O(m α(n)) の上限を初めて証明し^[1]、この上限が厳密であることも示した。1979年には、Galler-Fischer 木を含むポインタアルゴリズムの範囲での下界を示した^[7]。タージャンと van Leeuwen はより効率的なワンパスの Find のアルゴリズムも考案している^[2]。1989年、Fredman と Saks が、任意の素集合データ構造に対して Ω(α(n)) の下界を示し、素集合森の最適性が一般の計算モデル（セルプローブモデル）でも確定した^[3]。

1991年には、Galil と Italiano が素集合データ構造に関する調査論文を発表した^[13]。同じ1991年には、Richard J. Anderson と Heather Woll が、ブロックすることなく並列化した Union-Find（wait-free な並列アルゴリズム）を発表している^[18]。

2007年、ACM SIGPLAN の Workshop on ML において、Sylvain Conchon と Jean-Christophe Filliâtre が素集合森データ構造の永続版を発表した。これは構造の以前のバージョンを効率的に保持するもので、計算機支援証明システムCoqを使って形式的に正しさが証明されている^[15]。最も高速な実装は、非永続のアルゴリズムとほぼ同等の性能を達成しているが、計算量の解析は行われていない。

脚注・出典

1 2 3 4 5 6 7 8 9 Tarjan, Robert Endre (1975). “Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM 22 (2): 215–225. doi:10.1145/321879.321884.
1 2 3 4 Tarjan, Robert E.; van Leeuwen, Jan (1984). “Worst-case analysis of set union algorithms”. Journal of the ACM 31 (2): 245–281. doi:10.1145/62.2160.
1 2 3 M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pages 345–354. May 1989. "Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets."
1 2 3 4 5 6 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). “Chapter 21: Data structures for Disjoint Sets”. Introduction to Algorithms (Third ed.). MIT Press. ISBN 978-0-262-03384-8
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp.498–524.
1 2 Galler, Bernard A.; Fischer, Michael J. (1964-05). “An improved equivalence algorithm”. Communications of the ACM 7 (5): 301–303. doi:10.1145/364099.364331. 素集合森に関する最初の論文。
1 2 3 Tarjan, Robert Endre (1979). “A class of algorithms which require non-linear time to maintain disjoint sets”. Journal of Computer and System Sciences 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.
1 2 Hopcroft, J. E.; Ullman, J. D. (1973). “Set Merging Algorithms”. SIAM Journal on Computing 2 (4): 294–303. doi:10.1137/0202024.
↑ Blum, Norbert (1985). “On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem”. 2nd Symp. On Theoretical Aspects of Computer Science: 32–38.
↑ Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). “Worst-case and amortised optimality in union-find (Extended abstract)”. Proceedings of the thirty-first annual ACM symposium on Theory of Computing. pp. 499–506. doi:10.1145/301250.301383
↑ Alstrup, Stephen; Thorup, Mikkel; Gørtz, Inge Li; Rauhe, Theis; Zwick, Uri (2014). “Union-Find with Constant Time Deletions”. ACM Transactions on Algorithms 11 (1): 6:1–6:28. doi:10.1145/2636922.
↑ Ben-Amram, Amir M.; Yoffe, Simon (2011). “A simple and efficient Union-Find-Delete algorithm”. Theoretical Computer Science 412 (4–5): 487–492. doi:10.1016/j.tcs.2010.11.005.
1 2 3 Zvi Galil and Giuseppe F. Italiano. Data structures and algorithms for disjoint set union problems, ACM Computing Surveys, Volume 23, Issue 3 (September 1991), pages 319-344. ACM Digital Library
↑ Westbrook, Jeffery R.; Tarjan, Robert E. (1989). “Amortized Analysis of Algorithms for Set Union with Backtracking”. SIAM Journal on Computing 18 (1): 1–11. doi:10.1137/0218001.
1 2 Sylvain Conchon and Jean-Christophe Filliâtre. A Persistent Union-Find Data Structure. In ACM SIGPLAN Workshop on ML, Freiburg, Germany, October 2007. 論文ページ
↑ Gabow, Harold N.; Tarjan, Robert Endre (1985). “A linear-time algorithm for a special case of disjoint set union”. Journal of Computer and System Sciences 30 (2): 209–221. doi:10.1016/0022-0000(85)90014-5.
↑ Knight, Kevin (1989). “Unification: A multidisciplinary survey”. ACM Computing Surveys 21 (1): 93–124. doi:10.1145/62029.62030.
↑ Anderson, Richard J.; Woll, Heather (1991). Wait-free Parallel Algorithms for the Union-Find Problem. 23rd ACM Symposium on Theory of Computing. pp. 370–380. doi:10.1145/103418.103458.

外部リンク

C++ disjoint sets implementation, part of the Boost C++ libraries
Java implementation, part of JGraphT library
Disjoint Sets の可視化, by David Galles
Java applet: A Graphical Union-Find Implementation, by Rory L. P. McGuire

[Tarjan1975-1] 1 2 3 4 5 6 7 8 9 Tarjan, Robert Endre (1975). “Efficiency of a Good But Not Linear Set Union Algorithm”. Journal of the ACM 22 (2): 215–225. doi:10.1145/321879.321884.

[Tarjan1984-2] 1 2 3 4 Tarjan, Robert E.; van Leeuwen, Jan (1984). “Worst-case analysis of set union algorithms”. Journal of the ACM 31 (2): 245–281. doi:10.1145/62.2160.

[Fredman1989-3] 1 2 3 M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, pages 345–354. May 1989. "Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets."

[Cormen2009-4] 1 2 3 4 5 6 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). “Chapter 21: Data structures for Disjoint Sets”. Introduction to Algorithms (Third ed.). MIT Press. ISBN 978-0-262-03384-8

[IntroductionToAlgorithms-5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp.498–524.

[Galler1964-6] 1 2 Galler, Bernard A.; Fischer, Michael J. (1964-05). “An improved equivalence algorithm”. Communications of the ACM 7 (5): 301–303. doi:10.1145/364099.364331. 素集合森に関する最初の論文。

[Tarjan1979-7] 1 2 3 Tarjan, Robert Endre (1979). “A class of algorithms which require non-linear time to maintain disjoint sets”. Journal of Computer and System Sciences 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.

[Hopcroft1973-8] 1 2 Hopcroft, J. E.; Ullman, J. D. (1973). “Set Merging Algorithms”. SIAM Journal on Computing 2 (4): 294–303. doi:10.1137/0202024.

[9] Blum, Norbert (1985). “On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem”. 2nd Symp. On Theoretical Aspects of Computer Science: 32–38.

[10] Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). “Worst-case and amortised optimality in union-find (Extended abstract)”. Proceedings of the thirty-first annual ACM symposium on Theory of Computing. pp. 499–506. doi:10.1145/301250.301383

[11] Alstrup, Stephen; Thorup, Mikkel; Gørtz, Inge Li; Rauhe, Theis; Zwick, Uri (2014). “Union-Find with Constant Time Deletions”. ACM Transactions on Algorithms 11 (1): 6:1–6:28. doi:10.1145/2636922.

[12] Ben-Amram, Amir M.; Yoffe, Simon (2011). “A simple and efficient Union-Find-Delete algorithm”. Theoretical Computer Science 412 (4–5): 487–492. doi:10.1016/j.tcs.2010.11.005.

[Galil1991-13] 1 2 3 Zvi Galil and Giuseppe F. Italiano. Data structures and algorithms for disjoint set union problems, ACM Computing Surveys, Volume 23, Issue 3 (September 1991), pages 319-344. ACM Digital Library

[Westbrook1989-14] Westbrook, Jeffery R.; Tarjan, Robert E. (1989). “Amortized Analysis of Algorithms for Set Union with Backtracking”. SIAM Journal on Computing 18 (1): 1–11. doi:10.1137/0218001.

[Conchon2007-15] 1 2 Sylvain Conchon and Jean-Christophe Filliâtre. A Persistent Union-Find Data Structure. In ACM SIGPLAN Workshop on ML, Freiburg, Germany, October 2007. 論文ページ

[16] Gabow, Harold N.; Tarjan, Robert Endre (1985). “A linear-time algorithm for a special case of disjoint set union”. Journal of Computer and System Sciences 30 (2): 209–221. doi:10.1016/0022-0000(85)90014-5.

[Knight1989-17] Knight, Kevin (1989). “Unification: A multidisciplinary survey”. ACM Computing Surveys 21 (1): 93–124. doi:10.1145/62029.62030.

[Anderson1991-18] Anderson, Richard J.; Woll, Heather (1991). Wait-free Parallel Algorithms for the Union-Find Problem. 23rd ACM Symposium on Theory of Computing. pp. 370–380. doi:10.1145/103418.103458.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

定義