ei1333's page

ホーム > Wiki

素集合データ構造(Union-Find)

説明

集合を高速に扱うためのデータ構造。集合を合併する操作(unite), ある要素がどの集合に属しているか(find)を問い合わせる操作を行うことが出来る。

使い方

計算量

$O(\alpha(n))$

$\alpha$ はアッカーマンの逆関数

実装例

応用 1: 2部グラフの頂点彩色

Union-Find を用いると $2$ 部グラフ判定とその副作用として彩色が可能。頂点を倍長して偶奇に分ける。隣接頂点を同じ色にするときは, $\mathrm{unite}(u, v)$ と $\mathrm{unite}(u+N, v+N)$, 異なる色にするときは $\mathrm{unite}(u+N, v)$ と $\mathrm{unite}(u, v+N)$ をする。

応用 2: データ構造をマージする一般的なテク

データ構造をマージする一般的なテク(Weighted-Union-Heuristic) は, Union-Find の unite 操作で常に大きい木の根が全体の根になるよう連結する(union-by-rank) の考え方と同様。

補足: 経路圧縮, ランクによる統合の計算量

経路圧縮, ランクによる統合の $2$ つの工夫をすると計算量は $1$ クエリあたり $O(\alpha(n))$ となるが, 経路圧縮あるいはランクによる統合片方だけ行うと $O(\log n)$ となる。[証明: アルゴリズムとデータ構造 p268-270]

問題例

参考資料