Submission #4462269

---

Source Code Expand

class UnionFind:
    def __init__(self, n):
        # par[x]: x が根のときは x を含むグループのサイズ (の -1 倍)、そうでないときは親ノード
        self.par = [-1 for i in range(n + 1)]

    # 親ノードの検索
    def root(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # 併合
    # x と y を同じグループにする, 計算量はならし O(α(n))
    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x

    # x と y が同じグループにいるか, 計算量はならし O(α(n))
    def issame(self, x, y):
        return self.root(x) == self.root(y)

    # size(x): x を含むグループの所属メンバー数
    def size(self, x):
        return -self.par[self.root(x)]


if __name__ == '__main__':
    N, Q = list(map(int, input().split()))
    # print(Town.par)
    Town = UnionFind(N)
    for i in range(Q):
        P, A, B = map(int, input().split())
        if P == 0:
            Town.union(A, B)
        elif P == 1:
            if Town.issame(A, B):
                print('Yes')
            else:
                print('No')

Submission Info

Judge Result