[アルゴリズム]
Union-Find
木構造に似ているようで、実際は集合の分類に利用される。Union-FindやDisjoint-Setなどと呼ばれる。
- Union-Find Algorithm - Set 2 (Union By Rank and Path Compression)
- Find the number of Islands - Set 2 (Using Disjoint Set)
- www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/UnionFind.pdf
基本構造 (quick-union)
- Coursera Algorithmでは quick-union と呼ばれていた
- 後述するが、これだけではプロコンは突破できない…
- AOJは以下のコードだけで突破できる
- AOJ - DSL_1_A (Union-Find) を解いてみた
- #3016100 Solution for DSL_1_A by hiroyuking quick-union版: 処理時間 07:93 sec
- #3016394 Solution for DSL_1_A by hiroyuking 真のunion-find: 処理時間 00:22 sec
- 配列id
- 全体のノードを単純なint型の配列で表す
- root
- あるノードの最上位を求める
- unite
- ２つのノードを接続する
- same?
- ２つのノードが同じ集合内に所属するか調べる
| + | Union-Find木サンプルコード | |
計算量の削減 O(α(N))（経路圧縮とrankの実装）
ここからはAOJ本を読んで知ったこと及び、参考サイトで学んだことになる。
- 経路圧縮
- Union-Findである要素の最も上の親を求めるとき、途中までの要素を全て最上位の親に属していることに変える処理
- これにより、Union-Findのノードが多重に折り重なっていてもあとから親を求めるときに計算量が削減できる
def find_set(i, id)
if i != id[i]
id[i] = find_set(id[i], id)
end
id[i]
end
- rankの実装
- ２つの異なる木が存在して、それらが同一の親を持つ際に小さな木を大きな木にマージする処理
- これにより、親を求める処理の計算量を削減できる
UNION-BY-SIZE (x, y)
r ← FIND (x).
s ← FIND (y).
IF (r = s) RETURN.
ELSE IF (size(r) > size(s))
parent(s) ← r.
size(r) ← size(r) + size(s).
ELSE
parent(r) ← s.
size(s) ← size(r) + size(s).
上記は 蟻本 2-4 p.84にも書かれている。
参考：バイトの競プロメモ - ABC 049 D - 連結 / Connectivity
| + | Union-Find木サンプルコード O(α(N)) | |