素集合データ構造(Union-Find)
説明
集合を高速に扱うためのデータ構造。集合を合併する操作(unite), ある要素がどの集合に属しているか(find)を問い合わせる操作を行うことが出来る。
使い方
- $\mathrm{unite}(x, y)$: 集合 $x$ と $y$ を併合する. 併合済のとき $\mathrm{false}$, 未併合のとき $\mathrm{true}$ が返される
- $\mathrm{find(k)}$: 要素 $k$ が属する集合を求める
- $\mathrm{size(k)}$: 要素 $k$ が属する集合の要素の数を求める
計算量
$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
永続配列を使うとできる。
問題例
- 検証済ATC 001_B Union Find
- AOJ DSL_1_A 互いに素な集合
- 検証済(応用1)CF #383 C. Arpa’s overnight party and Mehrdad’s silent entering(Submittion: #24955808)
- 検証済(応用1)CF #400 D. The Door Problem(Submittion: #24955583)
- 検証済(応用4)AGC 002_D Stamp Rally