ATC B - Union Find
https://atcoder.jp/contests/atc001/tasks/unionfind_a
提出
code: python
n, q = map(int, input().split())
pab = list(map(int, input().split())) for _ in range(q)
class UnionFind:
def __init__(self, n):
# 親要素のノード番号を格納。parx == xの時そのノードは根(最初は全て根)
self.par = i for i in range(n)
# 木の高さを格納する（初期状態では0）
self.rank = 0 * n
# 人間の数
self.size = 1 * n
# 検索
def find(self, x):
# 根ならその番号を返す
if self.parx == x:
return x
# 根でないなら、親の要素で再検索
else:
# 走査していく過程で親を書き換える(return xが代入される)
self.parx = self.find(self.parx)
return self.parx
# 併合
def union(self, x, y):
# 根を探す
x = self.find(x)
y = self.find(y)
if x == y:
return
# 木の高さを比較し、低いほうから高いほうに辺を張る
if self.rankx < self.ranky:
self.parx = y
self.sizey += self.sizex
else:
self.pary = x
self.sizex += self.sizey
# 木の高さが同じなら片方を1増やす
if self.rankx == self.ranky:
self.rankx += 1
# 同じ集合に属するか判定
def same(self, x, y):
return self.find(x) == self.find(y)
UF = UnionFind(n)
for i in pab:
if i0 == 0:
UF.union(i1, i2)
else:
print("Yes") if UF.same(i1, i2) else print("No")
テーマ
#UnionFind
蟻本 2-4 食物連鎖