Submission #5627301

---

Source Code Expand

import sys
input = sys.stdin.readline

class UnionFindTree():
    def __init__(self, size):
        """
        Initializes `size` trees.
        size: size of union find tree
        """
        # initialize the map with n -> n
        self.__parent_map = range(size)

    def get_root(self, x):
        """
        Returns the root of tree which contains such given element.
        x: number of node
        """
        parent = self.__parent_map[x]
        if parent == x:
            return x
        else:
            root = self.get_root(parent)
            # shortens the finding path
            self.__parent_map[x] = root
            return root

    def unite(self, x, y):
        """
        combine two trees into one tree.
        """
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        # if x and y don't have the same root, combine then into one tree
        if root_x != root_y:
            self.__parent_map[x] = root_y

    def is_same(self, x, y):
        """
        Check the identity of given two tree.
        """
        root_x = self.get_root(x)
        root_y = self.get_root(y)
        return root_x == root_y

def main():
    n, q = map(int, input().split())
    tree = UnionFindTree(n)
    for _ in range(q):
        p, a, b = map(int, input().split())
        if p == 0:
            tree.unite(a - 1, b - 1)
        else:
            print('Yes' if tree.is_same(a - 1, b - 1) else 'No')

if __name__ == '__main__':
    main()

Submission Info

Judge Result