UnionFind
集合の併合と、共通の集合かどうかのチェックが高速なデータ構造。
グラフに辺を追加して、二頂点が連結かどうかのチェックが高速、という捉え方もできる。
N個の対象間の関係に関して、それがiffに分解できるならグラフの辺として記述できる
例えばグーチョキパーのいずれかである対象があったときに「xはyに勝つ」は、「xがグーである iff yがチョキである」のような3つのiffに分解できるので3Nの頂点集合に3本の辺を追加することに相当する
連結成分は条件を充足する解に相当する
iffでない場合→2-SAT
Related Pages
- →二分ヒープ×データ構造×ヒープキュー×優先度キュー×priority_queue×ある集合に値が追加削除される。最小の値を取得したい。×m個の数がn個の集合を移動する。集合の最小要素を得たい×n個の値が更新される、最小値を知りたい×ヒープのk番目の値を更新したい×中央値×best_kの取得→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]