Submission #3523254

---

Source Code Expand

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
Union Find
ATC001 B
"""

# using List
# n = upper bound of indices
n, q = map(int, input().split())

# In case where there are non-existent elemets
# parList = [-2]*n
# rankList = [1]*n

parList = [-1]*n
rankList = [1]*n


# In cases where there are non-existent elemets
# def addElement(i):
#    parList[i] = -1
#    rankList[i] = 1


def findRoot(i):
    par = parList[i]
    if par == -1:
        return i
    else:
        parpar = parList[par]
        while parpar != -1:
            parList[i] = parpar
            parpar = parList[parpar]
        return parList[i]


def isConnected(i1, i2):
    return findRoot(i1) == findRoot(i2)


def union(i1, i2):
    root1 = findRoot(i1)
    root2 = findRoot(i2)
    if not root1 == root2:
        if rankList[root1] <= rankList[root2]:
            parList[root1] = root2
        else:
            parList[root2] = root1
        if rankList[root1] == rankList[root2]:
            rankList[root2] += 1


for i in range(q):
    p, a, b = map(int, input().split())
    if p == 0:
        union(a, b)
    if p == 1:
        if isConnected(a, b):
            print('Yes')
        else:
            print('No')

Submission Info

Judge Result