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: Wrong Answer

Solution code:
# coding=utf-8


def unite(number1, number2, s_list):
    if number1 > number2:
        n1, n2 = number2, number1
    else:
        n1, n2 = number1, number2
    v2 = s_list[n2]
    for k in s_list:
        if s_list[k] == v2:
            s_list[k] = s_list[n1]
    print(s_list)
    return s_list


def is_same(number1, number2, s_list):
    print(s_list)
    if s_list[number1] == s_list[number2]:
        return True
    return False


def print_is_same(number1, number2, s_list):
    if is_same(number1, number2, s_list):
        print(1)
    else:
        print(0)


if __name__ == '__main__':
    n, q = map(int, input().split())
    set_list = {j: j for j in range(n)}

    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            set_list = unite(x, y, set_list)
        elif com == 1:
            print_is_same(x, y, set_list)

Submission status: Wrong Answer

Solution code:
p=[]
rank=[]
answer=[]

def makeset(x):
    p[x] = x
    rank[x] = 0
    
def union(x,y):
    link(findset(x),findset(y))
    
def link(x,y):
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] = rank[y] + 1
def findset(x):
    if x != p[x]:
        p[x] = findset(p[x])
    return p[x]

t,s = map(int,input().split())
for i in range(t):
    p.append(None)
    rank.append(None)
while True:
    try:
        o,x,y = map(int,input().split())
    except:
        break
    else:
        if o == 0:
            if p[x] == None:
                makeset(x)
            if p[y] == None:
                makeset(y)
            union(x,y)
            print(p[x])
            print(rank[x])
        else:
            if p[x] == None:
                makeset(x)
            if p[y] == None:
                makeset(y)
            if findset(x) == findset(y):
                answer.append(1)
            else:
                answer.append(0)
for i in range(len(answer)):
    print(answer[i])

Submission status: Wrong Answer

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]
            print sx
        elif y in s:
            iy = i
            sy = sets[i]
            print sy
    sets.pop(ix)
    sets.pop(iy - 1)
    sets.append(sx.union(sy))
    print sets


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: Wrong Answer

Solution code:
def create():
    data_x = []
    data_y = []
    index_x = 0
    index_y = 0
    index = 0
    for data in data_lis:
        if x in data:
            data_x = data
            index_x = index
        elif y in data:
            data_y = data
            index_y = index
        index += 1
        
        if data_x and data_y:
            break

    new_data = data_x + data_y
    
    if index_x < index_y:
        del data_lis[index_x]
        del data_lis[index_y-1]
    elif index_y < index_x:
        del data_lis[index_y]
        del data_lis[index_x-1]
        
    data_lis.append(new_data)
    
def check():
    for data in data_lis:
        if (x in data) and (y in data):
            result.append(1)
            break
    else:
        result.append(0)


if __name__ == '__main__':
    input_line = raw_input()
    n = int(input_line.split(' ')[0])
    q = int(input_line.split(' ')[1])
    
    data_lis = []
    for i in range(n):
        data_lis.append([i])
    
    result = []
    for i in range(q):
        input_line = raw_input()
        query = int(input_line.split(' ')[0])
        x = int(input_line.split(' ')[1])
        y = int(input_line.split(' ')[2])
        if query == 0:
            create()
        elif query == 1:
            check()
            
    for answer in result:
        print(answer)

Submission status: Wrong Answer

Solution code:
def create():
    data_x = []
    data_y = []
    index_x = 0
    index_y = 0
    index = 0
    for data in data_lis:
        if x in data:
            data_x = data
            index_x = index
        elif y in data:
            data_y = data
            index_y = index
        index += 1
        
        if data_x and data_y:
            break

    new_data = data_x + data_y
    
    if index_x < index_y:
        del data_lis[index_x]
        del data_lis[index_y-1]
    elif index_y < index_x:
        del data_lis[index_y]
        del data_lis[index_x-1]
        
    data_lis.append(new_data)
    
def check():
    for data in data_lis:
        if (x in data) and (y in data):
            print 1
            break
    else:
        print 0


if __name__ == '__main__':
    input_line = raw_input()
    n = int(input_line.split(' ')[0])
    q = int(input_line.split(' ')[1])
    
    data_lis = []
    for i in range(n):
        data_lis.append([i])
    
    result = []
    for i in range(q):
        input_line = raw_input()
        query = int(input_line.split(' ')[0])
        x = int(input_line.split(' ')[1])
        y = int(input_line.split(' ')[2])
        if query == 0:
            create()
        elif query == 1:
            check()

Submission status: Wrong Answer

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)
        print lis
    else:
        for s in lis:
            if (x in s) and (y in s):
                print 1
        else:
            print 0

Submission status: Wrong Answer

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
        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: Wrong Answer

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)
        return x

def unite(x,y):
    global rank,nodes
    if rank[nodes[x].parent]<rank[nodes[y].parent]:
        nodes[nodes[x].parent].parent=nodes[y].parent
    elif rank[nodes[x].parent]==rank[nodes[y].parent]:
        nodes[nodes[x].parent].parent=nodes[y].parent
        rank[y]+=1
    else:
        nodes[nodes[y].parent].parent=nodes[x].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: Wrong Answer

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)
        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: Wrong Answer

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
            if indexx >= 0 and indexy >= 0:
                break
        if indexx != indexy:
            s[indexx].extend(s[indexy])
            s.remove(s[indexy])
        print(s)
    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: Wrong Answer

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 parent[s1] == parent[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: Wrong Answer

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: Wrong Answer

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):
 		if self.num[i]==-1 or self.num[j]==-1:
 			return(False)
 		else:
 			return(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:
		if union.same(a,b):
			print(1)
		else:
			print(0)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

    def get_root(self,x):
        r = x
        depth = 0
        while self.parent[r]!=r:
            r = self.parent[r]
            depth += 1
        return r,depth

    def unite(self,x,y):
        rx,dx = self.get_root(x)
        ry,dy = self.get_root(y)
        if rx!=ry:
            if dx > dy:
                self.parent[ry] = rx
            else:
                self.parent[rx] = ry

    def same(self,x,y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        if rx==ry: return 1
        else: return 0


n,q = map(int,raw_input().split(' '))
tree = UnionFind(n)

answers = []
for _ in range(q):
    com,x,y = map(int,raw_input().split(' '))
    if com==0:
        tree.unite(x,y)
    elif com==1:
        answers.append(tree.same(x,y))

for a in answers:
    print a

Submission status: Wrong Answer

Solution code:
def unite(x, y, s_list):
    x_list = None
    y_list = None
    for s in s_list:
        if x in s and y in s:
            x_list = s.copy()
            y_list = s.copy()
            del s
        elif x in s:
            x_list = s.copy()
            del s
        elif y in s:
            y_list = s.copy()
            del s
        if x_list != None and y_list != None:
            break
    if x_list != None and y_list != None:
        s_list.append(list(set(x_list + y_list)))
    elif x_list != None and y_list == None:
        x_list.append(y)
        s_list.append(x_list)
    elif x_list == None and y_list != None:
        y_list.append(x)
        s_list.append(y_list)
    else:
        s_list.append([x, y])

def same(x, y, s_list):
    x_list = None
    y_list = None
    for s in s_list:
        if x in s and y in s:
            return 1
    return 0


n, q = list(map(int, input().split()))
com_list = list()
x_list = list()
y_list = list()
s_list = list()

for _ in range(q):
    com, x, y = list(map(int, input().split()))
    com_list.append(com)
    x_list.append(x)
    y_list.append(y)

for i in range(q):
    com = com_list[i]
    x = x_list[i]
    y = y_list[i]
    if com == 0:
        unite(x, y, s_list)
    else:
        result = same(x, y, s_list)
        print(result)

Submission status: Wrong Answer

Solution code:
testcase = """\
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"""


def main(fp):
    line = fp.readline()
    n, q = [int(x) for x in line.split()]
    s = [{i} for i in range(n)]
    for _ in range(q):
        command, x, y = [int(x) for x in fp.readline().split()]
        if command == 0:
            # unite
            s[x] = s[x] | s[y]
            s[y] = s[x]
        else:
            # same:
            if s[x] == s[y]:
                print("1")
            else:
                print("0")


if __name__ == "__main__":
    # import io
    # main(io.StringIO(testcase))

    import sys
    main(sys.stdin)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())

s =[set([i]) for i in range(n)]
p =[i for i in range(n)]

for i in range(q):
    com, x, y = map(int, input().split())
    if com:
        if y in s[p[x]]: print(1)
        else: print(0)
    else:
        s[p[x]] = s[p[x]] | s[p[y]]
        for j in range(n):
            if p[j] == p[y]: p[j] = p[x]

Submission status: Wrong Answer

Solution code:
n, nq = map(int, input().split())
set_list = list(range(n))

def find(n):
    global set_list
    if set_list[n] == n:
        return n
    result = set_list[n] = find(set_list[n])
    return result

def same(x, y):
    set_list[find(y)] = find(x)

def unite(x, y):
    return find(x) == find(y)

for _ in range(nq):
    com,x,y = map(int, input().split())
    if com == 0:
        same(x, y)
    else:
        if unite(x, y):
            print(0)
        else:
            print(1)

Submission status: Wrong Answer

Solution code:
#! python3
# disjoint_set_union_find_tree.py

n, q = [int(x) for x in input().split(' ')]

sets = [set([i]) for i in range(n)]

def unite(Sx, Sy):
    return Sx | Sy

def search(x):
    global sets
    flag = False
    for i in range(len(sets)):
        if x in list(sets[i]):
            flag = True
            break
    if flag:
        return i
    else:
        return None

def same(x, y):
    global sets
    flag = 0
    for set in sets:
        if x in set:
            if y in set:
                 flag = 1
            break
    return flag

for i in range(q):
    query, x, y = input().split(' ')
    x, y = int(x), int(y)
    if query == '0':
        # unite
        i_x = search(x)
        i_y = search(y)
        if i_x != None and i_y != None:
            sets[i_x] = unite(sets[i_x], sets[i_y])
            del sets[i_y]
    elif query == '1':
        # same
        print(same(x, y))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    n, q = (int(s) for s in stdin.readline().split())
    s = [[i] for i in range(n)]

    for _ in range(q):
        com, x, y = (int(s) for s in stdin.readline().split())
        if com:
            print(int(s[x] == s[y]))
        else:
            a = s[x]
            b = s[y]
            if a is not b:
                s[y] = a
                s[y][0] = b[0]


main()

Submission status: Wrong Answer

Solution code:
n,q = map(int, raw_input().split())
ls = [set([i]) for i in range(n)]
ref = [i for i in range(n)]
for i in range(q):
	com,x,y = map(int, raw_input().split())
	if com == 0: # unite
		ls[x] = ls[x]|ls[ref[y]]
		for i in list(ls[x]):
			ref[i] = ref[x]
	else: # same
		print 1 if y in ls[ref[x]] and x in ls[ref[y]] else 0

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


def unite(number1, number2, s_list):
    if number1 > number2:
        n1, n2 = number2, number1
    else:
        n1, n2 = number1, number2
    v2 = s_list[n2]
    for k in s_list:
        if s_list[k] == v2:
            s_list[k] = s_list[n1]
    return s_list


def is_same(number1, number2, s_list):
    if s_list[number1] == s_list[number2]:
        return True
    return False


def print_is_same(number1, number2, s_list):
    if is_same(number1, number2, s_list):
        print(1)
    else:
        print(0)


if __name__ == '__main__':
    n, q = map(int, input().split())
    set_list = {j: j for j in range(n)}

    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            set_list = unite(x, y, set_list)
        elif com == 1:
            print_is_same(x, y, set_list)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
N,Q = map(int,input().split())
rank = [0 for i in range(N)]

class Tree:
    def __init__(self,par,key):
        self.par = par
        self.key = key

List = [Tree(i,i) for i in range(N)]
for i in range(Q):
    com, x,y = map(int,input().split())
    while type(x) != int or List[x].par != x:
        x = List[x].par.key
    a = rank[x]
            
    while type(y) != int or List[y].par != y:
        y = List[y].par.key
    b = rank[y]

    if com == 0:
        if a <= b:
            if a == b:
                rank[x] += 1
            List[y].par = List[x]
            
        else:
            List[x].par = List[y]

    else:
        if x == y:
            print("1")
        else:
            print("0")

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import time

N,Q = map(int,input().split())
rank = [0 for i in range(N)]

class Tree:
    def __init__(self,par,key):
        self.par = par
        self.key = key

List = [Tree(i,i) for i in range(N)]
for i in range(Q):
    com, x,y = map(int,input().split())
    x1,y1 = x,y
    while List[x1].par != x1:
        x1 = List[x1].par
    a = rank[x1]
            
    while List[y1].par != y1:
        y1 = List[y1].par
    b = rank[y1]

    if com == 0:
        if a <= b:
            if a == b:
                rank[x1] += 1
            List[y1].par = x1
            
        else:
            List[x1].par = y1

    else:
        if x1 == y1:
            print("1")
        else:
            print("0")

Submission status: Time Limit Exceeded

Solution code:
class DisjointSet():
    def __init__(self):
        self.parent = None


def ancestor(elems, x):
    s = elems[x]
    while s.parent is not None:
        s = s.parent
    return s


def unite(elems, x, y):
    parent = DisjointSet()
    ancestor(elems, x).parent = parent
    ancestor(elems, y).parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class DisjointSet():
    def __init__(self):
        self.parent = None


def ancestor(elems, x):
    s = elems[x]
    while s.parent is not None:
        s = s.parent
    return s


def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        parent = DisjointSet()
        ax.parent = ay.parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


class DisjointSet():
    def __init__(self):
        self.parent = None


def ancestor(elems, x):
    s = elems[x]
    while s.parent is not None:
        s = s.parent
    return s


def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        parent = DisjointSet()
        ax.parent = ay.parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in stdin.readline().split()]
    elems = [DisjointSet() for _ in range(n)]

    for _ in range(q):
        com, x, y = [int(x) for x in stdin.readline().split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


class DisjointSet():
    def __init__(self):
        self.parent = None


def ancestor(elems, x):
    s = elems[x]
    while s.parent is not None:
        s = s.parent
    return s


def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        parent = DisjointSet()
        ax.parent = ay.parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in stdin.readline().split()]
    elems = [DisjointSet() for _ in range(n)]

    lines = stdin.readlines()
    for line in lines:
        com, x, y = [int(x) for x in line.split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


class DisjointSet():
    def __init__(self):
        self.parent = None
        self.ancestor = self


def ancestor(elems, x):
    s = elems[x].ancestor
    while s.parent is not None:
        s = s.parent
    s.ancestor = s
    return s


def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        parent = DisjointSet()
        ax.parent = ay.parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


def unite(sets, x, y):
    sx = [s for s in sets if x in s][0]
    sy = [s for s in sets if y in s][0]
    if sx == sy:
        return sets
    else:
        newSets = []
        newSets.append(set.union(sx, sy))
        newSets += [s for s in sets if x not in s and y not in s]
        return newSets


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


def main():
    elemNum, queryNum = map(int, raw_input().rstrip().split())
    sets = [set([i]) for i in range(elemNum)]
    for _ in range(queryNum):
        qType, x, y = map(int, raw_input().rstrip().split())
        if qType == 0:
            sets = unite(sets, x, y)
        else:
            print same(sets, x, y)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding=utf-8


def unite(sets, x, y):
    sx = [s for s in sets if x in s][0]
    # print sx
    if y in sx:
        return sets
    else:
        newSets = [s for s in sets if x not in s and y not in s]
        sy = [s for s in sets if y in s][0]
        # print sy
        newSets.append(set.union(sx, sy))
        return newSets


def same(sets, x, y):
    sx = [s for s in sets if x in s][0]
    if y in sx:
        return 1
    else:
        return 0


def main():
    elemNum, queryNum = map(int, raw_input().rstrip().split())
    sets = [set([i]) for i in range(elemNum)]
    for _ in range(queryNum):
        qType, x, y = map(int, raw_input().rstrip().split())
        if qType:
            print same(sets, x, y)
        else:
            sets = unite(sets, x, y)
            # print sets


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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
        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: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

set_list = [{i} for i in range(n)]
set_dict = list(range(n))

while q:
    op, x, y = map(int, input().split())
    if op:
        print(1 if set_dict[x] == set_dict[y] else 0)
    else:
        idx_x, idx_y = set_dict[x], set_dict[y]
        set_y = set_list[idx_y]

        for i in set_y:
            set_dict[i] = idx_x
        set_list[idx_x] |= set_y

    q -= 1

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

class UnionFindTree:
    def __init__(self, x):
        self.parent = self
        self.id = x

    def find(self):
        if self.id == self.parent.id:
            return self
        else:
            return self.parent.find()


# main
n, q = map(int, input().split())
nodes = [UnionFindTree(i) for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split())
    x_root = nodes[x].find()
    y_root = nodes[y].find()
    if com == 0:
        # union
        y_root.parent = x_root
    else:
        # same
        same = 1 if x_root.id == y_root.id else 0
        print(same)