Submission #473861

---

Source Code Expand

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
#roitiさんをまるまるパクリ
import time
import sys
import io
import re
import math
import itertools
import collections
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.141592653589
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
#start = time.clock()
class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par=range(size)
        self.g_num=size

    def find(self, x):
    #木の根を求める
        if x==self.par[x]:
        #根
            return x
        #経路圧縮
        self.par[x]=self.find(self.par[x])
        return self.par[x]

    def same(self, x, y):
    #xとが同じ集合に属するか否か
        return self.find(x)==self.find(y)

    def unite(self, x, y):
    #xとyの属する集合を併合
        x,y=self.find(x),self.find(y)
        if x==y:
            return

        self.g_num-=1
        if self.rank[x]>self.rank[y]:
            self.par[y]=x
        else:
            self.par[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def group_num(self):
        return self.g_num


N,Q=map(int,raw_input().split())
uf=UnionFind(N)

for loop in xrange(Q):
    p,a,b=map(int,raw_input().split())
    if p==0:
        uf.unite(a,b)
    else:
        print 'Yes' if uf.same(a,b) else 'No'

Submission Info

Judge Result