Submission #5074676

---

Source Code Expand

# coding: utf-8
class UnionFindTree(object):
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        rx = self.find(x)
        ry = self.find(y)

        if rx == ry:
            return

        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        else:
            self.parent[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1

    def same(self, x, y):
        rx = self.find(x)
        ry = self.find(y)

        return rx == ry


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

tree = UnionFindTree(N)

for i in range(Q):
    P, A, B = map(int, input().split())
    if P == 0:
        tree.unite(A, B)
    else:
        if tree.same(A, B):
            print("Yes")
        else:
            print("No")

Submission Info

Judge Result