Problem:


Disjoint Set

Write a program which manipulates a disjoint set S = {S1, S2, . . . , Sk}.

First of all, the program should read an integer n, then make a disjoint set where each element consists of 0, 1, ... n&minus;1 respectively.

Next, the program should read an integer q and manipulate the set for q queries. There are two kinds of queries for different operations:

unite(x, y): unites sets that contain x and y, say Sx and Sy, into a new set.

same(x, y): determine whether x and y are in the same set.

Input

n q
com1 x1 y1
com2 x2 y2
...
comq xq yq

In the first line, n and q are given. Then, q queries are given where com represents the type of queries. '0' denotes unite and '1' denotes same operation. 

Output

For each same operation, print 1 if x and y are in the same set, otherwise 0, in a line.

Constraints

1 ≤ n ≤ 10000

1 ≤ q ≤ 100000

x &ne; y

Sample Input

5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0

Sample Output

0
0
1
1
1
0
1
1



Sample input:
5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0


Sample output:
0
0
1
1
1
0
1
1

Submission status: Accepted

Solution code:
class UFT(object):
    def __init__(self):
        self.par={i:i for i in range(10001)}
        self.rank={i:0 for i in range(10001)}
    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def unite_chk(self,a,b):
        return self.find(a)==self.find(b)
        
obj=UFT()
n,q=map(int,input().split())
for _ in range(q):
    c,x,y=map(int,input().split())
    if c:
        print(int(obj.unite_chk(x,y)))
    else:
        obj.unite(x,y)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
class DisjointSets:
    '''
    Implementing disjoint sets using disjoint sets forests structure.

    --- methods ---
    __init__(size): size should be the number of elements in this disjoint sets
    unite(x, y): unite sets that contain x and y into a new set
    same(x, y): check if x and y are in the same set
    '''

    def __init__(self, size):
        self.ranks = [0] * size
        self.roots = [0] * size
        for x in range(size):
            self._make_set(x)

    def _make_set(self, x):
        self.roots[x] = x
        self.ranks[x] = 0

    def _link(self, x, y):
        if self.ranks[x] > self.ranks[y]:
            self.roots[y] = x
        else:
            self.roots[x] = y
            if self.ranks[x] == self.ranks[y]:
                self.ranks[y] += 1

    def _find_set(self, x):
        # compression of the path
        if x != self.roots[x]:
            self.roots[x] = self._find_set(self.roots[x])

        return self.roots[x]

    def unite(self, x, y):
        if self.same(x, y):
            raise SameSetError('{} and {} are in the same set'.format(x, y))
        
        self._link(self._find_set(x), self._find_set(y))

    def same(self, x, y):
        return self._find_set(x) == self._find_set(y)


class SameSetError(Exception):
    pass


if __name__ == '__main__':
    import sys
    n, q = map(int, input().split())
    ds = DisjointSets(n)

    for line in sys.stdin.readlines():
        query, x, y = map(int, line.strip().split())
        if query == 0:
            ds.unite(x, y)
        elif query == 1:
            if ds.in_same_set(x, y):
                print(1)
            else:
                print(0)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
class DisjointSets:
    '''
    Implementing disjoint sets using disjoint sets forests structure.

    --- methods ---
    __init__(size): size should be the number of elements in this disjoint sets
    unite(x, y): unite sets that contain x and y into a new set
    same(x, y): check if x and y are in the same set
    '''

    def __init__(self, size):
        self.ranks = [0] * size
        self.roots = [0] * size
        for x in range(size):
            self._make_set(x)

    def _make_set(self, x):
        self.roots[x] = x
        self.ranks[x] = 0

    def _link(self, x, y):
        if self.ranks[x] > self.ranks[y]:
            self.roots[y] = x
        else:
            self.roots[x] = y
            if self.ranks[x] == self.ranks[y]:
                self.ranks[y] += 1

    def _find_set(self, x):
        # compression of the path
        if x != self.roots[x]:
            self.roots[x] = self._find_set(self.roots[x])

        return self.roots[x]

    def unite(self, x, y):
        if self.same(x, y):
            raise SameSetError('{} and {} are in the same set'.format(x, y))

        self._link(self._find_set(x), self._find_set(y))

    def same(self, x, y):
        return self._find_set(x) == self._find_set(y)


class SameSetError(Exception):
    pass


if __name__ == '__main__':
    import sys
    n, q = map(int, input().split())
    ds = DisjointSets(n)

    for line in sys.stdin.readlines():
        query, x, y = map(int, line.strip().split())
        if query == 0:
            ds.unite(x, y)
        elif query == 1:
            if ds.same(x, y):
                print(1)
            else:
                print(0)

Submission status: Runtime Error

Solution code:
from sys import exit
class UnionFind():
    #負の値は根で集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        if self.table[x] < 0:return x
        root = self.find(self.table[x])
        self.table[x] = root
        return root

    #併合
    def union(self,x,y):
        s1 = self.find(x)#代表のIndexを取得する
        s2 = self.find(y)
        if s1 != s2:#代表のIndexが違う場合
            if self.table[s1] < self.table[s2]:#要素数の多い方へMergeする
                self.table[s2] += self.table[s1]#子の和を増やす(-)
                self.table[s1] = s2#Mergeされる側の代表をする側のインデックスに
            else:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
        return
    def size(self,x):
        return -self.table[self.find(x)]
N,Q = [int(n) for n in input().split()]
c = [0]*Q
x = [0]*Q
y = [0]*Q
UF = UnionFind(N)
for i in range(Q):
    c[i], x[i], y[i] = [int(n) for n in input().split()]
    if(c[i] == 0):
        UF.union(x[i],y[i])
    else:
        print(1 if UF.find(x[i]) == UF.find(y[i]) else 0)

Submission status: Runtime Error

Solution code:
import sys
f = sys.stdin

def unite(x, y):
    global dat
    x, y = find(dat, x), find(dat, y)
    if x != y:
        dat[x] = y

def same(x, y):
    global dat
    x, y = find(dat, x), find(dat, y)
    print(1 if x == y else 0)
def find(dat, x):
    if dat[x] < 0:
        return x
    dat[x] = find(dat, dat[x])
    return dat[x]

com = (unite, same)

n, q = map(int, f.readline().split())
dat = [-1] * n

for c, x, y in (map(int, f.readline().split()) for _ in range(q)):
    com[c](x, y)

Submission status: Runtime Error

Solution code:
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):
        return self.find(x) == self.find(y)

    def unite(self, 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 i in xrange(q):
    c, x, y = map(int, raw_input().split())
    if c == 0: uf.unite(x, y)
    else: print int(uf.same(x, y))

Submission status: Runtime Error

Solution code:
# coding=utf-8

elemNum, queryNum = map(int, raw_input().rstrip().split())
sets = [set([i]) for i in range(elemNum)]


def unite(x, y):
    for i, s in enumerate(sets):
        if x in s:
            ix = i
            sx = sets[i]
        elif y in s:
            iy = i
            sy = sets[i]
    sets.pop(ix)
    sets.pop(iy - 1)
    sets.append(sx.union(sy))


def same(x, y):
    for s in sets:
        if x in s and y in s:
            return 1
    else:
        return 0

for _ in range(queryNum):
    qType, x, y = map(int, raw_input().rstrip().split())
    if qType == 0:
        unite(x, y)
    else:
        print same(x, y)

Submission status: Runtime Error

Solution code:
n, q = map(int, raw_input().split())
lis = []
for i in range(n):
    lis.append(set(str(i)))
for i in range(q):
    c, x, y = raw_input().split()
    if c == '0':
        index1 = index2 = None
        for i, s in enumerate(lis):
            if x in s:
                index1 = i
            elif y in s:
                index2 = i
        newSet = lis[index1] | lis[index2]
        if index1 < index2:
            del lis[index1]
            del lis[index2-1]
        else:
            del lis[index2]
            del lis[index1-1]
        lis.append(newSet)
    else:
        for s in lis:
            if (x in s) and (y in s):
                print 1
                break
        else:
            print 0

Submission status: Runtime Error

Solution code:
n, q = map(int, raw_input().split())
lis = []
for i in range(n):
    lis.append(set([str(i)]))
for i in range(q):
    c, x, y = line.rstrip().split()
    if c == '0':
        index1 = index2 = None
        for i, s in enumerate(lis):
            if x in s:
                index1 = i
            elif y in s:
                index2 = i
        else:
            if (index1 == None) or (index2 == None):
                continue
        newSet = lis[index1] | lis[index2]
        if index1 < index2:
            del lis[index1]
            del lis[index2-1]
        else:
            del lis[index2]
            del lis[index1-1]
        lis.append(newSet)
    else:
        for s in lis:
            if (x in s) and (y in s):
                print 1
                break
        else:
            print 0

Submission status: Runtime Error

Solution code:
def find(x):
    global set_list
    return x if set_list[x] == x else find(set_list[x])


n, q = map(int, input().split())
set_list = list(range(n))

while q:
    op, x, y = map(int, input().split())
    if op:
        print(1 if find(x) == find(y) else 0)
    else:
        if x > y:
            x, y = y, x
        set_list[find(y)] = x

    q -= 1

Submission status: Runtime Error

Solution code:
def find(x):
    global set_list
    return x if set_list[x] == x else find(set_list[x])


n, q = map(int, input().split())
set_list = list(range(n))

while q:
    op, x, y = map(int, input().split())
    if op:
        print(1 if find(x) == find(y) else 0)
    else:
        if x > y:
            x, y = y, x
        set_list[find(y)] = find(x)

    q -= 1

Submission status: Runtime Error

Solution code:
def findset(x):
    global nodes
    if nodes[x].parent==x:
        return x
    else:
        nodes[x].parent=findset(nodes[x].parent)
        return nodes[x].parent

def unite(x,y):
    global rank,nodes
    if rank[nodes[x].parent]<rank[nodes[y].parent]:
        nodes[nodes[x].parent].parent=nodes[nodes[y].parent].parent
    elif rank[nodes[x].parent]==rank[nodes[y].parent]:
        nodes[nodes[x].parent].parent=nodes[nodes[y].parent].parent
        rank[y]+=1
    else:
        nodes[nodes[y].parent].parent=nodes[nodes[x].parent].parent

def same(x,y):
    global nodes
    findset(x)
    findset(y)
    if nodes[x].parent==nodes[y].parent:
        print(1)
    else:
        print(0)

n,q=map(int,raw_input().split())
rank=[0]*n
nodes=[]
for i in xrange(n):
    fac=node(i)
    nodes.append(fac)
for i in xrange(q):
    com,x,y=map(int,raw_input().split())
    if com==0:
        unite(x,y) 
    else:
        same(x,y)

Submission status: Runtime Error

Solution code:
class node:
    def __init__(self,parent):
        self.parent=parent

def findset(x):
    global nodes
    if nodes[x].parent==x:
        return x
    else:
        nodes[x].parent=findset(nodes[x].parent)

def unite(x,y):
    global rank,nodes
    findset(x)
    findset(y)
    if rank[nodes[x].parent]<rank[nodes[y].parent]:
        nodes[nodes[x].parent].parent=nodes[nodes[y].parent].parent
    elif rank[nodes[x].parent]==rank[nodes[y].parent]:
        nodes[nodes[x].parent].parent=nodes[nodes[y].parent].parent
        rank[y]+=1
    else:
        nodes[nodes[y].parent].parent=nodes[nodes[x].parent].parent

def same(x,y):
    global nodes
    findset(x)
    findset(y)
    if nodes[x].parent==nodes[y].parent:
        print(1)
    else:
        print(0)

n,q=map(int,raw_input().split())
rank=[0]*n
nodes=[]
for i in xrange(n):
    fac=node(i)
    nodes.append(fac)
for i in xrange(q):
    com,x,y=map(int,raw_input().split())
    if com==0:
        unite(x,y) 
    else:
        same(x,y)

Submission status: Runtime Error

Solution code:
class UnionFind:

    def __init__(self, *xs):
        self.p = {}
        self.rank = {}
        self.make_set(xs)

    def make_set(self, *xs):
        for x in xs:
            self.p[x] = x
            self.rank[x] = 0

    def union(self, x, y):
        self.link(self.find_set(x), self.find_set(y))

    def find_set(self, x):
        p = self.p
        if x != p[x]:  # path compression
            p[x] = self.find_set(p[x])
        return p[x]

    def is_same_set(self, x, y):
        return self.find_set(x) == self.find_set(y)

    def link(self, x, y):
        p, rank = self.p, self.rank
        if rank[x] > rank[y]:
            p[y] = x
        else:
            p[x] = y
            if rank[x] == rank[y]:
                rank[y] += 1


n, q = input()
uf = UnionFind(*range(n))
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        uf.union(x, y)
    else:
        print(1 if uf.is_same_set(x, y) else 0)

Submission status: Runtime Error

Solution code:
n,q = map(int, input().split())
s = [[i] for i in range(n)]
for i in range(q):
    com,x,y = map(int, input().split())
    if com == 0:
        indexx,indexy = -1,-1
        for j in range(len(s)):
            if x in s[j]:
                indexx = j
            if y in s[j]:
                indexy = j
        s[indexx].extend(s[indexy])
        s.remove(s[indexy])
    if com == 1:
        for j in range(len(s)):
            if x in s[j]:
                if y in s[j]:
                    print(1)
                else:
                    print(0)
                break

Submission status: Runtime Error

Solution code:
import sys

f_i = sys.stdin

n, q = map(int, f_i.readline().split())

S = [[i] for i in range(n)]

for l in f_i:
    com, x, y = map(int, l.split())
    for e in S:
        if x in e and y in e:
            if com == 1:
                print(1)
            break
        elif x in e:
            if com == 0:
                ex = e
            else:
                print(0)
                break
        elif y in e:
            if com == 0:
                ey = e
            else:
                print(0)
                break
    if com == 0:
        S.append(ex + ey)
        S.remove(ex)
        S.remove(ey)

Submission status: Runtime Error

Solution code:
import sys

f_i = sys.stdin

n, q = map(int, f_i.readline().split())

S = set([frozenset([i]) for i in range(n)])

def unite(sets, v1, v2):
    s1 = None
    s2 = None
    for s in sets:
        if v1 in s and v2 in s:
            return None
        elif v1 in s:
            s1 = s
        elif v2 in s:
            s2 = s
        if s1 and s2:
            break
    sets.discard(s1)
    sets.discard(s2)
    s3 = s1.union(s2)
    sets.update(s3)

def same(sets, v1, v2):
    for s in sets:
        if v1 in s and v2 in s:
            print(1)
            break
        elif v1 in s or v2 in s:
            print(0)
            break

for l in f_i:
    com, x, y = map(int, l.split())
    if com == 0:
        unite(S, x, y)
    else:
        same(S, x, y)

Submission status: Runtime Error

Solution code:
def find_group(x):
    return [x in g for g in groups].index(True)

n, q = map(int, raw_input().split())
groups = [set([i]) for i in range(n)]

for i in range(q):
    com, x, y = map(int, raw_input().split())
    if com == 0:
        ind1 = find_group(x)
        g1 = groups.pop(ind1)
        
        ind2 = find_group(y)
        g2 = groups.pop(ind2)
        
        groups.append(g1.union(g2))
        
    elif com == 1:
        ind1 = find_group(x)
        ind2 = find_group(y)
        
        print int(ind1 == ind2)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split(" "))
items = [i for i in range(n)]
parent = [i for i in range(n)]

def root(s):
    if parent[s] == s:
        return s
    else:
        parent[s] = root(parent[s])
        return parent[s]

def same(s1, s2):
    if root[s1] == root[s2]:
        print("1")
    else:
        print("0")

def unite(s1, s2):
    s1 = root(s1)
    s2 = root(s2)

    if s1 == s2:
        return

    parent[s1] = s2


for i in range(q):
    query, item1, item2 = input().split(" ")
    item1, item2 = int(item1), int(item2)

    if query == "0":
        unite(item1, item2)
    else:
        same(item1, item2)


    parent[s1] = s2


for i in range(q):
    query, item1, item2 = input().split(" ")
    item1, item2 = int(item1), int(item2)

    if query == "0":
        unite(item1, item2)
    else:
        same(item1, item2)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split(" "))
items = [i for i in range(n)]
parent = [i for i in range(n)]

def root(s):
    if parent[s] == s:
        return s
    else:
        parent[s] = root(parent[s])
        return parent[s]

def same(s1, s2):
    if root(s1) == root(s2):
        print("1")
    else:
        print("0")

def unite(s1, s2):
    s1 = root(s1)
    s2 = root(s2)

    if s1 == s2:
        return

    parent[s1] = s2


for i in range(q):
    query, item1, item2 = input().split(" ")
    item1, item2 = int(item1), int(item2)

    if query == "0":
        unite(item1, item2)
    else:
        same(item1, item2)

Submission status: Runtime Error

Solution code:
# ?????????O(n)????????£???????????????
class union_find(object):
 	"""union-find tree"""
 	def __init__(self, length):
 		self.length = length
 		self.unionnumber=0
 		self.unionlist=[[]]
 		self.num=list(-1 for i in range(length))

 	def unite(self,i,j):
 		if self.num[i]==-1:
 			if self.num[j]==-1:
 				self.unionlist[self.unionnumber].extend([i,j])
 				self.num[i]=self.unionnumber
 				self.num[j]=self.unionnumber
 				self.unionnumber+=1
 				self.unionlist.append([])
 			else:
 				tmp=i 
 				i=j 
 				j=tmp 
 		if self.num[i]!=-1:
 			if self.num[j]!=-1:
 				if self.num[i]==self.num[j]:
 					pass
 				else:
 					self.unionlist[self.num[i]].extend(self.unionlist[self.num[j]])
 					tmp=self.num[j]
 					for k in self.unionlist[self.num[j]]:
 						self.num[k]=self.num[i]
 					self.unionlist[tmp]="del"
 			else:
 				self.num[j]=self.num[i]
 				self.unionlist[self.num[i]].append(j)

 	def same(self,i,j):
 		print(self.num[i]==self.num[j])


n,m=input().split()
n=int(n)
m=int(m)

l=[]
union=union_find(n)
for i in range(m):
	com,a,b=input().split()
	a=int(a)
	b=int(b)
	if com="unite":
		union.unite(a,b)
	else:
		union.same(a,b)

Submission status: Runtime Error

Solution code:
def root(x,rt):
    if rt[x] == x:
        return x
    else:
        while rt[x] != x:
            rt[x] = root(rt[x],rt)
            return rt[x]
def union(x,y,rt,rank):
    rootx = rt[x]
    rooty = rt[y]
    if rootx == rooty:
        return 0
    else:
        if rank[rootx] < rank[rooty]:
            rt[rooty] = rootx
        else:
            rt[rootx] = rooty
            if rank[rootx] == rank[rooty]:
                rank[rootx] += 1

def issame(x,y,rt):
    return root(x,rt) == root(y,rt)

length,query = (int(n) for n in input().split(" "))
rootlist = [n for n in range(length)]
rank = [0 for n in range(length)]

for q in range(query):
    #print(root)
    com,x,y = (int(n) for n in input().split(" "))
    if com == 0:
        union(x,y,rootlist,rank)
    else:
        print(1 if issame(x,y,rootlist) else 0)

Submission status: Runtime Error

Solution code:
def root(x,rt):
    if rt[x] == x:
        return x
    else:
        while rt[x] != x:
            rt[x] = root(rt[x],rt)
            return rt[x]
def union(x,y,rt,rank):
    rootx = root(x,rt)
    rooty = root(y,rt)
    if rootx == rooty:
        return 0
    else:
        if rank[rootx] < rank[rooty]:
            rt[rooty] = rootx
        else:
            rt[rootx] = rooty
            if rank[rootx] == rank[rooty]:
                rank[rootx] += 1

def issame(x,y,rt):
    return root(x,rt) == root(y,rt)

length,query = (int(n) for n in input().split(" "))
rootlist = [n for n in range(length)]
rank = [0 for n in range(length)]

for q in range(query):
    #print(root)
    com,x,y = (int(n) for n in input().split(" "))
    if com == 0:
        union(x,y,rootlist,rank)
    else:
        print(1 if issame(x,y,rootlist) else 0)

Submission status: Runtime Error

Solution code:
import sys

def solve():
    n, q = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    ans = []

    for lp in range(q):
        c, x, y = map(int, sys.stdin.readline().split())

        if c == 0:
            uf.unite(x, y)
        else:
            ans.append(1 if uf.is_same(x, y) else 0)

    print(*ans, sep='\n')


class UnionFind:

    def __init__(self, n):
        self.ds = [i for i in range(n)]
        self.root = [i for i in range(n)]
        # self.rank = [0] * n

    def find_root(self, x):
        if x != self.root[x]:
            self.root[x] = self.find_root(self.root[x])

        return self.root[x]

    def is_same(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def unite(self, x, y):
        p = self.find_root(x)
        q = self.find_root(y)
        self.root[p] = q

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
class DisjoinSet:
    def __init__(self, size):
        self.rank = [0 for _ in range(size)]
        self.p = [0 for _ in range(size)]
        for i in range(n):
            self.makeSet(i)

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = x

    def same(self, x, y):
        print(int(self.findSet(x) == self.findSet(y)))

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    # ???????±???????
    def findSet(self, x):
        if x != self.p[x]:
            self.p[x] = self.findSet(self.p[x])
        return self.p[x]


if __name__ == '__main__':
    n, q = map(int, input().split())
    D = DisjoinSet(n)
    cmd = {0: lambda x, y: D.unite(x, y), 1: lambda x, y: D.same(x, y)}
    for _ in range(q):
        c, x, y = map(int, input().split())
        cmd[c](x, y)

Submission status: Runtime Error

Solution code:
PARENT = {}

def MAKE_SET(v):
    PARENT.update({v : v})

def FIND_SET(u):
    if PARENT[u] == u:
        return u
    else:
        return FIND_SET(PARENT[u])

def UNION(u, v):
    u_root = FIND_SET(u) 
    v_root = FIND_SET(v)
    PARENT[u_root] = v_root

def SAME(u, v):
    return FIND_SET(u) == FIND_SET(v)

n, q = raw_input().split(' ')
for i in range(int(n)):
    MAKE_SET(i)

for _ in range(int(q)):
    query_type, x, y = raw_input().split(' ')

    if query_type == '0':
        # unite
        UNION(int(x), int(y))

    else:
        # same:
        if SAME(int(x), int(y)):
            print 1
        else:
            print 0

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

tree = [[-1, 1]  for _ in range(N)] # [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0])
    
    return group

def unite(x, y):
    px = find(x)
    py = find(y)
    
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px

for _ in range(Q):
    com, x, y = tuple(map(int, input().split()))
    if com: # same
        print(int(find(x) == find(y)))
    else: # unite
        unite(x, y)

Submission status: Runtime Error

Solution code:
# encoding: "utf-8"

class Unreachable(Exception):
    pass

def main():
    [n, q] = [int(x) for x in input().split()]
    setlist = list()
    for i in range(n):
        setlist.append(set(i))

    for _ in range(q):
        run(setlist)


def run(setlist):
    com, x, y = [int(x) for x in input().split()]
    if com == 0:
        # unite
        new_set = setlist[x] | setlist[y]
        for i in new_set:
            setlist[i] = new_set

    elif com == 1:
        # same
        if y in setlist[x]:
            print(1)
        else:
            print(0)
    else:
        raise Unreachable

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# encoding: "utf-8"

class Unreachable(Exception):
    pass


class SetManager:
    def __init__(self, n):
        self.data = list()
        for i in range(n):
            self.data.append((i, {i}))

    def ref(self, i):
        return self.data[i][1]

    def set(self, i, value):
        self.data[i] = (i, value)

    def find_set(self, i):
        value = self.ref(i)
        if isinstance(value, set):
            return self.data[i]
        elif isinstance(value, int):
            result = self.find_set(value)
            self.set(i, result[0])
            return result
        else:
            raise Unreachable

    def run(self, command):
        com, x, y = command
        if com == 0:
            # unite
            i, setx = self.find_set(x)
            j, sety = self.find_set(y)
            new_set = setx | sety
            self.set(i, new_set)
            self.set(j, i)

        elif com == 1:
            # same
            if y in self.find_set(x)[1]:
                print(1)
            else:
                print(0)
        else:
            raise Unreachable

def main():
    n, q = [int(x) for x in input().split()]
    manager = SetManager(n)

    commands = list()
    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        commands.append((com, x, y))
    
    for command in commands:
        manager.run(command)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.rank = [1 for i in range(n)]

    def root(self, v):
        if self.parent[v] == v:
            self.parent[v] = v    
        else:
            self.parent[v] = self.root(self.parent[v]) 
        
        return self.parent[v]

    def same(self, u, v):
        return self.root(u) == self.root(v)

    def is_root(self, v):
        return self.root(v) == v

    def unite(self, u, v):
        if self.same(u, v):
            return
        
        u = self.root(u)
        v = self.root(v)
        if self.rank[u] > self.rank[v]:
            u, v = v, u
        
        self.rank[u] += self.rank[v]
        self.parent[v] = u

    def element_count(self, v):
        return self.rank[self.root(v)]

def main():
    n, q = map(int, input().split())
    uf = UnionFind(n)

    for i in range(q):
        com, x, y = map(int, input().split())

        if com == 0:
            uf.unite(x, y)
        else:
            print(1 if uf.same(x, y) else 0)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def is_in_sameset(S, x, y) :
    if x <= S and y <= S :
        return True
    else :
        return False


def main() :
    n, q = [int(i) for i in input().split()]
    set_list = [{i} for i in range(n)]

    com = []
    x = []
    y = []

    for _ in range(q) :
        tmp = input().split()
        com.append(int(tmp[0]))
        x.append(int(tmp[1]))
        y.append(int(tmp[2]))



    for i in range(q) :
        if com[i] == 0 :
            set1 = set()
            set2 = set()
            for set_item in set_list :
                if set([x[i]]) <= set_item :
                    set1 = set_item
                    #set_list.remove(set_item)
                if set([y[i]]) <= set_item :
                    set2 = set_item
                    #set_list.remove(set_item)

            union_set = set1 | set2
            set_list.remove(set1)
            set_list.remove(set2)
            set_list.append(union_set)
        elif com[i] == 1 :
            flag = False
            for set_item in set_list :
                if is_in_sameset(set_item, set([x[i]]), set([y[i]])) :
                    flag = True
            if flag :
                print("1")
            else :
                print("0")


if __name__ == '__main__' :
    main()

Submission status: Runtime Error

Solution code:
# It took me about 40 minutes to finsih this assignment.
# The task itself is relatively simple, since we have sample code on handouts.
# One problem I met was that in case 22, I had a "RecursionError" (maximum recursion depth exceeded in comparison).
# The solution was simple: import sys, and add a line "sys.setrecursionlimit(100000)".

#import sys

line = input().split()
n = int(line[0])
q = int(line[1])
mat = [0]*n
for i in range(n):
	mat[i]=i
#sys.setrecursionlimit(100000)

def root(a):
	if mat[a]==a:
		return a
	else:
		mat[a] = root(mat[a])
		return mat[a]

def union(a, b):
	mat[root(a)]=root(b)

def is_same(a,b):
	if root(a) == root(b):
		return 1
	else:
		return 0

for i in range(q):
	line = input().split()
	a = int(line[0])
	line[1]=int(line[1])-1
	line[2]=int(line[2])-1
	if a==0:
		union(mat[line[1]],mat[line[2]])
	if a==1:
		print(is_same(mat[line[1]],mat[line[2]]))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.rank = [0]*n
        self.parent = [i for i 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 merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[y] = x
        elif self.rank[x] > self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[x] = y
            self.rank[y] += 1
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

n, q = map(int, input().split())
uf = UnionFind(n)
for i in range(q):
    com, x, y = map(int, input().split())
    
    if com == 0:
        uf.merge(x, y)
    else:
        print(1 if uf.same(x, y) else 0)