- Union-Find は素集合データ構造とも呼ばれ、複数の要素をグループに分けて管理し、「2つの要素が同じグループか」「2つのグループを1つにまとめる」という操作を、ほぼ定数時間で処理できます。
- 内部は木の集まりとして表現され、各ノードが親へのポインタを持ちま、木の根がそのグループの代表元（representative）になります。
- path compression と union by rank という2つの最適化を組み合わせることで、操作あたりの計算量が O(α(n)) と現実的な入力サイズでは 4 以下にとどまります。
1. Union-Findとは？
Union-Findは、グループ分けされた要素を管理するデータ構造です1。
Union-Findは、以下の2つの操作に特化しています。
- 「この2つは同じグループか」という判定
- 「この2つのグループを1つにまとめる」という統合
もともとはコンパイラの変数管理という実務的な問題から生まれました。
ほかにも、グラフの連結性判定や最小全域木の構築など、幅広い場面で使われています。
メリットは、操作の計算量はほぼ定数で、どれだけ操作を繰り返しても遅くならないこと。
シンプルな配列2本で実装でき、コードも短くまとまります。
プログラミングの問題で「グループの統合と判定」が絡むときには、役立つかもしれません。
1.1. どんな問題を解くか
「Union-Find」が使えるのは、N個の要素がいくつかのグループに分かれていて、グループの統合と同一性判定を繰り返したい場面です。
たとえば、次のような問題を考えてみます。
N人の人がいる。
Q個のクエリを順に処理せよ。
1 u v— u と v を同じグループにする2 u v— u と v が同じグループならYES、そうでなければNOを出力する
制約: N, Q ≤ 100,000
たとえば、N=5 で、5個のクエリを処理した場合はこうなります。
1 1 2 → 1 と 2 を同じグループにする → {1,2} {3} {4} {5}
1 3 4 → 3 と 4 を同じグループにする → {1,2} {3,4} {5}
2 1 3 → 1 と 3 は同じグループか？ → NO
1 2 3 → 2 と 3 を同じグループにする → {1,2,3,4} {5}
2 1 3 → 1 と 3 は同じグループか？ → YES1.2. なぜ素朴な実装では間に合わないか
各要素にグループIDを割り当てる配列を使うとします。
(defun solve/naive (n queries)
(let ((group (make-array (1+ n) :initial-element nil)))
(dotimes (i (1+ n)) (setf (aref group i) i))
(loop for (type u v) in queries
do (ecase type
(1
(let ((gu (aref group u))
(gv (aref group v)))
(dotimes (i (1+ n))
(when (= (aref group i) gu)
(setf (aref group i) gv)))))
(2
(if (= (aref group u) (aref group v))
(print "YES")
(print "NO")))))))Code language: Lisp (lisp)グループ統合のたびに全要素を走査するので、クエリ1回が O(N) になります。
Q 個のクエリ全体では O(N × Q) です。
N = Q = 100,000 のとき、単純計算で100億回の操作になり、時間内に終わりません2。
これを O(Q α(N)) で処理できるのが Union-Find です。
2. Union-Find の構造
Union-Find は木の集まり、すなわち森として素集合を表現します。
各木が1つのグループに対応し、根がそのグループの代表です。
各ノードは親へのポインタだけを持ちます。
子へのポインタは不要で、根は自分自身を親とします3。
初期状態（N=5）:
1 2 3 4 5 ← 各ノードが根（自分が代表）
1と2を統合後:
1 3 4 5
|
2 ← 2の親が1になる
さらに3と4を統合後:
1 3 5
| |
2 4「u と v が同じグループか」を調べるには、それぞれの根を辿って比較します。
「u と v を統合する」には、一方の根をもう一方の根の子にします。
3. Common Lisp 実装
3.1. データ構造を作る
parent 配列と rank 配列の2本を使います4。
(defun make-uf (n)
;; 1-indexed で n 要素分の Union-Find を作る
(let ((parent (make-array (1+ n)))
(rank (make-array (1+ n) :initial-element 0)))
(dotimes (i (1+ n))
(setf (aref parent i) i)) ; 最初は自分が根
(list parent rank)))Code language: Lisp (lisp)3.2. 根を探す（uf-find）
ノードから根まで親を辿り続けて、根のインデックスを返します。
(defun uf-find (uf x)
(let ((parent (first uf)))
(if (= (aref parent x) x)
x
(uf-find uf (aref parent x)))))Code language: Lisp (lisp)2の根を探す場合、2 から 1 へ辿り、1 は自分が根なので 1 を返します5。
3.3. グループを統合する（uf-union!）
2つのノードの根を求め、一方の根をもう一方の子にします。
(defun uf-union! (uf x y)
(let* ((parent (first uf))
(rank (second uf))
(rx (uf-find uf x))
(ry (uf-find uf y)))
(unless (= rx ry)
(cond ((< (aref rank rx) (aref rank ry))
(setf (aref parent rx) ry))
((> (aref rank rx) (aref rank ry))
(setf (aref parent ry) rx))
(t
(setf (aref parent ry) rx)
(incf (aref rank rx)))))))Code language: Lisp (lisp)3.4. 同じグループか判定する（uf-same?）
(defun uf-same? (uf x y)
(= (uf-find uf x) (uf-find uf y)))Code language: Lisp (lisp)3.5. まとめて使う
冒頭の問題を解きます。
(defun solve (n queries)
(let ((uf (make-uf n)))
(loop for (type u v) in queries
do (ecase type
(1 (uf-union! uf u v))
(2 (if (uf-same? uf u v)
(format t "YES~%")
(format t "NO~%")))))))Code language: Lisp (lisp)(solve 5
'((1 1 2)
(1 3 4)
(2 1 3) ; NO
(1 2 3)
(2 1 3))) ; YES
;=> NO
;=> YESCode language: Lisp (lisp)4. EQUIVALENCE宣言の連鎖判定に考案された
Union-Find は 1964年、Bernard A. Galler と Michael J. Fischer が論文 “An Improved Equivalence Algorithm” で発表したのが起源です6。
動機は、コンパイラの実装上の問題でした。
Fortran の EQUIVALENCE 宣言は「この変数とあの変数を同じメモリ領域に置く」という指示です7。
複数の EQUIVALENCE 宣言が連鎖した場合、どの変数が同じ領域を共有するかを効率よく判定する必要がありました。
Galler と Fischer はこの「等価性の伝播」を木構造で管理するアルゴリズムを提案しました。
当時の計算量解析は不完全で、正確な上限はしばらく不明のままでした。
1973年に Hopcroft と Ullman が O(log* n) を証明し8、1975年に Robert Tarjan が O(α(n)) という現在知られている上限を初めて示しました。
1979年にはこの上限が、特定のアルゴリズムクラスにおける下限でもあることを証明しています。
コンパイラの実装上の問題から生まれたデータ構造が、アルゴリズム解析の発展を促した例のひとつです。
4.1. path compression で木を平たくする
素朴な uf-find では、木が深くなると根までの経路が長くなります。
最悪の場合、N個の要素が1本のチェーンになり、find が O(N) になります。
悪い例:
1 ← 2 ← 3 ← 4 ← 5 (5の根を探すのに4ステップかかる)path compression はこれを防ぎます。
根を返すついでに、経路上の全ノードの親を直接根に書き換えます9。
find(5) を呼ぶと:
before: 1 ← 2 ← 3 ← 4 ← 5
after: 1 ← 2
1 ← 3 (書き換え)
1 ← 4 (書き換え)
1 ← 5 (書き換え)次回以降、同じ経路を辿る操作が1ステップで終わります。
(defun uf-find (uf x)
(let ((parent (first uf)))
(if (= (aref parent x) x)
x
;; 根を求めながら、親を根に付け替える
(setf (aref parent x) (uf-find uf (aref parent x))))))Code language: Lisp (lisp)4.2. union by rank で木を低く保つ
path compression だけでも十分速いですが、union の方向を制御すると木がより平坦に保たれます10。
union by rank は、rank（木の深さの上限）が小さい方を大きい方の子にします。
同じ rank どうしを統合する場合だけ、片方の rank を 1 増やします。
rank 1 の木と rank 2 の木を統合する場合:
A (rank=2) A (rank=2)
/ \ → /|\
B C (rank=1) B C D
|
Drank が大きい木を根に据えることで、結果の木の深さが不必要に増えません。
(defun uf-union! (uf x y)
(let* ((parent (first uf))
(rank (second uf))
(rx (uf-find uf x))
(ry (uf-find uf y)))
(unless (= rx ry)
(cond
;; rank が小さい方を大きい方の子にする
((< (aref rank rx) (aref rank ry))
(setf (aref parent rx) ry))
((> (aref rank rx) (aref rank ry))
(setf (aref parent ry) rx))
;; rank が同じなら片方の rank を上げる
(t
(setf (aref parent ry) rx)
(incf (aref rank rx)))))))Code language: Lisp (lisp)path compression と union by rank を両方使うと、操作あたり O(α(n)) になります。
4.3. 逆アッカーマン関数の計算オーダーはほぼ定数
O(α(n)) の α(n) は、逆アッカーマン関数です。
アッカーマン関数は非常に速く増大する関数です。
そのため、その逆関数は極めてゆっくりとしか増えません11。
宇宙の原子数はおよそ 10^80 ですが、α(10^80) ≤ 4 です。
現実的なあらゆる入力サイズで α(n) は 4 以下にとどまるので、計算量の記述としては「ほぼ定数」と読んで差し支えありません。
この上限を 1975年に初めて証明したのが Robert Tarjan で、1979年にはこれが下限でもあることを示しました。
Union-Find は理論的にも実用的にも最適なデータ構造として確立されています。
5. 応用：Kruskal 法との組み合わせ
Union-Find の使い方のひとつが、Kruskal 法による最小全域木の構築です。
最小全域木は英語で Minimum Spanning Tree、MST と略します12。
最小全域木は、重み付きグラフの全頂点を、重みの合計が最小になるように木でつなぐ問題です。
Kruskal 法はエッジを重み順に見ていき、サイクルを作らないエッジだけを選びます。
このとき「エッジの両端が既につながっているか」の判定に Union-Find を使います。
(defun kruskal (n edges)
"edges は (重み 頂点u 頂点v) のリスト。
MST の総重みを返す。
"
(let ((uf (make-uf n))
(total 0)
(count 0))
(loop for (w u v) in (sort edges #'< :key #'first)
;; サイクルを作らないエッジだけ採用する
when (not (uf-same? uf u v))
do (uf-union! uf u v)
(incf total w)
(incf count)
until (= count (1- n))) ; n-1 本選んだら完成
total))Code language: Lisp (lisp)エッジを重み順にソートしてから Union-Find で連結判定するので、全体の計算量は O(E log E) です。
;; 4頂点のグラフ
(kruskal 4
'((1 1 2) ; 辺(1,2) 重み1
(3 1 3) ; 辺(1,3) 重み3
(2 2 3) ; 辺(2,3) 重み2
(4 3 4) ; 辺(3,4) 重み4
(5 2 4))) ; 辺(2,4) 重み5
;=> 7 （辺(1,2)+(2,3)+(3,4) = 1+2+4）Code language: Lisp (lisp)ソートがボトルネックになります13。
6. Union-Findのコード
(defun make-uf (n)
(let ((parent (make-array (1+ n)))
(rank (make-array (1+ n) :initial-element 0)))
(dotimes (i (1+ n))
(setf (aref parent i) i))
(list parent rank)))
(defun uf-find (uf x)
(let ((parent (first uf)))
(if (= (aref parent x) x)
x
(setf (aref parent x) (uf-find uf (aref parent x))))))
(defun uf-union! (uf x y)
(let* ((parent (first uf))
(rank (second uf))
(rx (uf-find uf x))
(ry (uf-find uf y)))
(unless (= rx ry)
(cond ((< (aref rank rx) (aref rank ry))
(setf (aref parent rx) ry))
((> (aref rank rx) (aref rank ry))
(setf (aref parent ry) rx))
(t
(setf (aref parent ry) rx)
(incf (aref rank rx)))))))
(defun uf-same? (uf x y)
(= (uf-find uf x) (uf-find uf y)))Code language: Lisp (lisp)- Disjoint Set Union（DSU）とも呼ばれます。競技プログラミングのコミュニティでは DSU という略称がよく使われます。 – Disjoint-set data structure – Wikipedia
- 競技プログラミングでは 1秒あたりおよそ 10^8〜10^9 回の単純な操作が目安です。100億回はその10〜100倍にあたります。 – AtCoder 計算量の目安（AtCoder Library Practice Contest 解説）
- この表現方法は Galler-Fischer trees とも呼ばれます。 – Disjoint-set data structure – Wikipedia
- rank の代わりにグループのサイズを使う union by size という手法もあります。小さい方を大きい方の子にするという方針は同じで、計算量も同じ O(α(n)) です。実装によってはサイズの方が直感的で扱いやすい場合があります。 – Disjoint Set Union – Algorithms for Competitive Programming
- この実装は再帰を使っているため、木が非常に深くなるとスタックオーバーフローのリスクがあります。path compression を加えた版（後述）では実用上ほぼ問題になりませんが、念のためループ版に書き換えることもできます。 – Disjoint Set Union – Algorithms for Competitive Programming
- 論文は Communications of the ACM Volume 7, Issue 5 に掲載されました。DOI は 10.1145/364099.364331 です。 – An improved equivalence algorithm – ACM Digital Library
- 論文ではこのアルゴリズムが従来手法より計算時間を40%削減したと報告されています。 – An improved equivalence algorithm – ACM Digital Library
- log* n は反復対数（iterated logarithm）と呼ばれ、「n が 1 以下になるまで対数を繰り返し適用した回数」と定義されます。n ≤ 2^65536 という宇宙の原子数をはるかに超える範囲でも log* n ≤ 5 にとどまります。 – Iterated logarithm – Wikipedia
- path compression の変種として、path splitting（経路上の全ノードを祖父母に向け直す）と path halving（1つおきのノードだけ祖父母に向け直す）があります。どちらも最悪時間計算量は同じです。Tarjan と Van Leeuwen が提案しました。 – Disjoint-set data structure – Wikipedia
- path compression と union by rank の最適化は McIlroy と Morris が開発し、Tritter も独立に同じ手法を考案しました。 – Disjoint Set Union – Algorithms for Competitive Programming
- α(n) が 5 以上になるのは n がアッカーマン関数の値を超えるときで、そのような数は宇宙のスケールをはるかに超えます。log* n も同様に極端に遅い関数ですが、α(n) はさらにその下を行きます。 – Inverse Ackermann function – gabrielnivasch.org
- Kruskal 法は数学者 Joseph B. Kruskal が 1956年に論文 “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem” で発表しました。Proceedings of the American Mathematical Society に掲載された2ページ足らずの短い論文です。 – On the shortest spanning subtree of a graph – Semantic Scholar
- 同じ最小全域木問題を解くアルゴリズムとして Borůvka 法があり、並列化に向いています。1926年にチェコの数学者 Otakar Borůvka が Moravia 地方の電力網設計問題を解くために考案したもので、Kruskal 法より30年早い発表です。 – 17 On the Shortest Spanning Subtree of a Graph – IEEE Xplore