DSU
無向グラフに対して、
- 辺の追加
- $2$ 頂点が連結かの判定
をならし $O(\alpha(n))$ 時間で処理することが出来ます。
また、内部的に各連結成分ごとに代表となる頂点を $1$ つ持っています。辺の追加により連結成分がマージされる時、新たな代表元は元の連結成分の代表元のうちどちらかになります。
コンストラクタ
d = initDSU(n:int):DSU
- $n$ 頂点 $0$ 辺の無向グラフを作ります。
制約
- $0 \leq n \leq 10^8$
計算量
- $O(n)$
merge
d.merge(a:int, b:int):int
辺 $(a, b)$ を足します。
$a, b$ が連結だった場合はその代表元、非連結だった場合は新たな代表元を返します。
制約
- $0 \leq a < n$
- $0 \leq b < n$
計算量
- ならし $O(\alpha(n))$
same
d.same(a:int, b:int):bool
頂点 $a, b$ が連結かどうかを返します。
制約
- $0 \leq a < n$
- $0 \leq b < n$
計算量
- ならし $O(\alpha(n))$
leader
d.leader(a:int):int
頂点 $a$ の属する連結成分の代表元を返します。
制約
- $0 \leq a < n$
計算量
- ならし $O(\alpha(n))$
size
d.size(a:int):int
頂点 $a$ の属する連結成分のサイズを返します。
制約
- $0 \leq a < n$
計算量
- ならし $O(\alpha(n))$
groups
d.groups():seq[seq[int]]
グラフを連結成分に分け、その情報を返します。
返り値は「「一つの連結成分の頂点番号のリスト」のリスト」です。 (内側外側限らず)vector内でどの順番で頂点が格納されているかは未定義です。
計算量
- $O(n)$
使用例
AC code of https://atcoder.jp/contests/practice2/tasks/practice2_a
import atcoder/header
import atcoder/dsu
let n, q = nextInt()
var d = initDSU(n)
for i in 0..<q:
let t, u, v = nextInt()
if t == 0:
d.merge(u, v)
else:
if d.same(u, v):
echo 1
else:
echo 0
日本語API（試験的）
import "atcoder/extra/ja/structure/素集合データ構造"
var uf = 素集合データ構造を初期化(n)
discard uf.併合(a, b)
doAssert uf.同じ集合か(a, b)
正式APIの initDSU, merge, same,
leader, size, groups もそのまま利用できます。