dsu

dsu

disjoint set union,つまりUnionFind木です. 主な使用例としては,最小全域木問題をクラスカル法で解くときなどに使います.

初期化

G=dsu(N)

ここで,Nは頂点の数です.

merge

G.merge(a,b)

頂点aがある連結成分と頂点bがある連結成分を合体します.

same

G.same(a,b)

これは,「頂点aと頂点bが同じ連結成分」ならばTrue,そうでないならばFalseを返します.

leader

G.leader(a)

aの連結成分の代表元を返します.

size

G.size(a)

aの連結成分にある頂点数(aを含む)を答えます.

groups

G.groups()

グラフの連結成分の情報を答えます.

使用例

使用例1

(https://atcoder.jp/contests/practice2/tasks/practice2_a)

class dsu():
    #(中略)
N,Q=map(int,input().split())
G=dsu(N)
for i in range(Q):
    t,u,v=map(int,input().split())
    if t==0:
        G.merge(u,v)
    else:
        print(1 if G.same(u,v) else 0)

入力例1に対する出力

0
1
0
1

使用例2

class dsu():
    #(中略)

N=10
G=dsu(N)
print([G.leader(i) for i in range(N)])
for i in range(5):
    G.merge(2*i,2*i+1)
print([G.leader(i) for i in range(N)])
G.merge(1,3)
print(G.size(0))
print(G.groups())

出力

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 0, 2, 2, 4, 4, 6, 6, 8, 8]
4
[[0, 1, 2, 3], [4, 5], [6, 7], [8, 9]]