Disjoint Set Union（Union-Find／素集合データ構造）
集合の併合と同一集合判定を高速に行います。
一般にはDisjoint Set UnionまたはUnion-Findと呼ばれます。このページはatcoder/dsuの日本語facadeを説明します。
import
import atcoder/extra/ja/structure/素集合データ構造
使用例
var dsu = 素集合データ構造を初期化(6)discard dsu.併合(0, 1)discard dsu.併合(1, 2)doAssert dsu.同じ集合か(0, 2)echo dsu.代表元(0)echo dsu.集合の大きさ(0)echo dsu.集合一覧()API対応表
| 日本語API | 元のAPI |
|---|---|
素集合データ構造 |
DSU |
素集合データ構造を初期化 |
initDSU |
併合 |
merge |
同じ集合か |
same |
代表元 |
leader |
集合の大きさ |
size |
集合一覧 |
groups |
基本操作は償却
[ O(\alpha(n)) ]
です。集合一覧は (O(n)) です。