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]

応用 3: UnionFindに何かをもたせるやつ

左端と右端をもたせたUnionFind の実装例を以下にあげる。

応用 4: 部分永続UnionFind

$t$ 番目のクエリを処理した時点における頂点 $x$ が含まれる連結成分の根や大きさを求めるクエリを $O(\log n)$ で行うことができる。

応用 5: 完全永続UnionFind

永続配列を使うとできる。

問題例

参考資料