A66 - Connect Query
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bn
解答
code: python
class unionfind:
# n 頂点の Union-Find 木を作成
# （ここでは頂点番号が 1-indexed になるように実装しているが、0-indexed の場合は par, size のサイズは n でよい）
def __init__(self, n):
self.n = n
self.par = -1 * (n + 1) # 最初は親が無い
self.size = 1 * (n + 1) # 最初はグループの頂点数が 1
# 頂点 x の根を返す関数
def root(self, x):
# 1 個先（親）がなくなる（つまり根に到達する）まで、1 個先（親）に進み続ける
while self.parx != -1:
x = self.parx
return x
# 要素 u, v を統合する関数
def unite(self, u, v):
rootu = self.root(u)
rootv = self.root(v)
if rootu != rootv:
# u と v が異なるグループのときのみ処理を行う
if self.sizerootu < self.sizerootv:
self.parrootu = rootv
self.sizerootv += self.sizerootu
else:
self.parrootv = rootu
self.sizerootu += self.sizerootv
# 要素 u と v が同一のグループかどうかを返す関数
def same(self, u, v):
return self.root(u) == self.root(v)
N, Q = map(int, input().split())
queries = list(map(int, input().split())) for i in range(Q)
uf = unionfind(N)
for tp, u, v in queries:
if tp == 1:
uf.unite(u, v)
if tp == 2:
if uf.same(u, v):
print("Yes")
else:
print("No")