acl_cpp.dsu

dsu.dsu

# dsu
from acl_cpp.dsu import dsu

無向グラフに対して、

辺の追加
\(2\) 頂点が連結かの判定

をならし \(O(\alpha(n))\) 時間で処理することが出来ます。

ここで、\(\alpha(n)\) はアッカーマン関数の逆関数で、ほとんど定数時間とみなせます。

また、内部的に各連結成分ごとに代表となる頂点を \(1\) つ持っています。辺の追加により連結成分がマージされる時、新たな代表元は元の連結成分の代表元のうちどちらかになります。

コンストラクタ

# dsu::dsu(int n)
def dsu(n: int = 0) -> dsu

\(n\) 頂点 \(0\) 辺の無向グラフを作ります。

制約

\(0 \le n \lt 2^{31}\)

計算量

\(O(n)\)

dsu.merge

# void dsu::merge(int a, int b)
def dsu.merge(a: int, b: int) -> None

辺 \((a, b)\) を足します。

\(a, b\) が連結だった場合はその代表元、非連結だった場合は新たな代表元を返します。

制約

\(0 \le a \lt n\)
\(0 \le b \lt n\)

計算量

ならし \(O(\alpha(n))\)

dsu.same

# bool dsu::same(int a, int b)
def dsu.same(a: int, b: int) -> bool

頂点 \(a, b\) が連結かどうかを返します。

制約

\(0 \le a \lt n\)
\(0 \le b \lt n\)

計算量

ならし \(O(\alpha(n))\)

dsu.leader

# int dsu::leader(int a)
def dsu.leader(a: int) -> int

頂点 \(a\) の属する連結成分の代表元を返します。

制約

\(0 \le a \lt n\)

計算量

ならし \(O(\alpha(n))\)

dsu.size

# int dsu::size(int a)
def dsu.size(a: int) -> int

頂点 \(a\) の属する連結成分のサイズを返します。

制約

\(0 \le a \lt n\)

計算量

ならし \(O(\alpha(n))\)

dsu.groups

# vector<vector<int>> dsu::groups()
def dsu.groups() -> list[list[int]]

グラフを連結成分に分け、その情報を返します。

返り値は「「一つの連結成分の頂点番号のリスト」のリスト」です。（内側外側限らず）vector 内でどの順番で頂点が格納されているかは未定義です。

計算量

\(O(n)\)

使用例

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_a

from acl_cpp.dsu import dsu

N, Q = map(int, input().split())
d = dsu(N)

for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        d.merge(u, v)
    else:
        print(int(d.same(u, v)))