FreeStyleWiki

Union-Find木

[アルゴリズム]

Union-Find

木構造に似ているようで、実際は集合の分類に利用される。Union-FindやDisjoint-Setなどと呼ばれる。

  基本構造 (quick-union)

  • Coursera Algorithmでは quick-union と呼ばれていた
    • 後述するが、これだけではプロコンは突破できない…
    • AOJは以下のコードだけで突破できる
配列id
全体のノードを単純なint型の配列で表す
root
あるノードの最上位を求める
unite
2つのノードを接続する
same?
2つのノードが同じ集合内に所属するか調べる

+ 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の実装
    • 2つの異なる木が存在して、それらが同一の親を持つ際に小さな木を大きな木にマージする処理
    • これにより、親を求める処理の計算量を削減できる
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))