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:
# -*- coding: utf-8 -*-
class UnionFind:
    def __init__(self,size):
        self.parent=range(size)#???????????????????????????
        self.tree_num=size#??¨????????¨?????°
        self.tree_w=[1]*size#????????????????????????????±???????????????¨??????????????°
        self.rank=[0]*size#??¨?????????

    def findset(self,x):#????????¢????????????x??????????????§?????£???????????????????????????????????????
        if self.parent[x]==x:
            return x
        else:
            self.parent[x]=self.findset(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):#x,y?????????
        x=self.findset(x)
        y=self.findset(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.parent[x]=y
            self.tree_num-=1
            self.tree_w[y]+=self.tree_w[x]
        else:
            self.parent[y]=x
            self.tree_num-=1
            self.tree_w[x]+=self.tree_w[y]
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1

    def same(self,x,y):#x,y???????????¨????±????????????????????????????
        if self.findset(x)==self.findset(y):
            return True
        else:
            return False

    def tree_number(self):#??¨????????¨?????°
        return self.tree_num

    def tree_weight(self,x):#x????±?????????¨??????????????°
        return self.tree_w[self.findset(x)]

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

Submission status: Accepted

Solution code:
#! /usr/local/bin/python

class N:
	def __init__(self, n):
		self.parent = n
		self.rank = 0
		self.n = n

def find( n: int) -> N:
	if data[n].parent == n:
		return data[n]
	else:
		data[n].parent = find(data[n].parent).n
		return data[data[n].parent]

def union( a: int, b: int):
	A = find(a)
	B = find(b)
	if A.rank > B.rank:
		B.parent = A.n
	elif A.rank < B.rank:
		A.parent = B.n
	elif A.n != B.n:
		B.parent = A.n
		A.rank = A.rank + 1

# Start
n, p = input().split(" ")
data = [ N(i) for i in range(int(n))]
for i in range(int(p)):
	com, x, y = input().split(" ")
	if com == '0':
		union(int(x),int(y))
	else:
		if find(int(x)).n != find(int(y)).n:
			print(0)
		else:
			print(1)

Submission status: Accepted

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.add(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: Accepted

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.add(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: Accepted

Solution code:
import sys
 
f_i = sys.stdin
 
n, q = map(int, f_i.readline().split())

class DisjointSets:
    def __init__(self, size):
        self.size = size
        self.representatives = list(range(size))

    def _find(self, x):
        return self.representatives[x]

    def union(self, x, y):
        x1 = self._find(x)
        y1 = self._find(y)
        if x1 == y1:
            return None
        # unite Sx and Sy
        for i in range(self.size):
            if self.representatives[i] == y1:
                self.representatives[i] = x1

    def isSameSet(self, x, y):
        if self._find(x) == self._find(y):
            print(1)
        else:
            print(0)

S = DisjointSets(n)

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

Submission status: Accepted

Solution code:
import sys

f_i = sys.stdin

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

class DisjointSets:
    def __init__(self, size):
        # negative values are roots(representatives of each tree)
        # positive values represent the parent element
        self.table = [-1 for _ in range(size)]

    def _find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # compression of the path
            self.table[x] = self._find(self.table[x])
            return self.table[x]

    def uniteSets(self, x, y):
        s1 = self._find(x)
        s2 = self._find(y)
        if s1 != s2:
            if self.table[s1] < self.table[s2]: # the smaller has more elements
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2

    def isSameSet(self, x, y):
        if self._find(x) == self._find(y):
            print(1)
        else:
            print(0)

S = DisjointSets(n)

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

Submission status: Accepted

Solution code:
import sys
 
f_i = sys.stdin
 
n, q = map(int, f_i.readline().split())

class DisjointSets:
    def __init__(self, size):
        # negative values are roots(representatives of each tree)
        # positive values represent the parent element
        self.table = [-1 for _ in range(size)]

    def _find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self._find(x)
        s2 = self._find(y)
        if s1 != s2:
            if self.table[s1] < self.table[s2]: # the smaller has more elements
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2

    def isSameSet(self, x, y):
        if self._find(x) == self._find(y):
            print(1)
        else:
            print(0)

S = DisjointSets(n)

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

Submission status: Accepted

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

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

    if rank[s1] < rank[s2]:
        parent[s1] = s2
    else:
        parent[s2] = s1
        if rank[s1] == rank[s2]:
            rank[s1] += 1

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: Accepted

Solution code:
def find(x):
    if tree[x] < 0:
        return x
    tree[x] = find(tree[x])
    return tree[x]


def unite(x, y):
    x_position = find(x)
    y_position = find(y)
    if x_position == y_position:
        return True
    if y_position < x_position:
        x_position, y_position = y_position, x_position
    tree[x_position] += tree[y_position]
    tree[y_position] = x_position
    return False


def same(x, y):
    if find(x) == find(y):
        print(1)
    else:
        print(0)


n, q = map(int, input().split())
tree = [-1] * n
for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        unite(x, y)
    if com == 1:
        same(x, y)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""


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

output:
0
0
1
1
1
0
1
1

"""

import sys


class UnionFind(object):
    __slots__ = ('size', 'rank', 'p_list')

    def __init__(self, size):
        self.size = int(size)
        self.rank = [0] * self.size
        self.p_list = [i for i in range(self.size)]

    def find_set(self, x):
        if x != self.p_list[x]:
            self.p_list[x] = self.find_set(self.p_list[x])
        return self.p_list[x]

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

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

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


def action(cmd):
    for _, each in enumerate(cmd):
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.unite(ele_1, ele_2)
        elif cmd == 1:
            if case.same(ele_1, ele_2):
                print('1')
            else:
                print('0')
    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    ele_num, cmd_num = map(int, _input[0].split())
    cmd_list = map(lambda x: x.split(), _input[1:])

    case = UnionFind(size=ele_num)

    ans = action(cmd_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""


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

output:
0
0
1
1
1
0
1
1

"""

import sys


class UnionFind(object):
    __slots__ = ('size', 'rank', 'p_list')

    def __init__(self, size):
        self.size = int(size)
        self.rank = [0] * self.size
        self.p_list = [i for i in range(self.size)]

    def _find(self, x):
        if x != self.p_list[x]:
            self.p_list[x] = self._find(self.p_list[x])
        return self.p_list[x]

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

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

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


def action(cmd):
    for _, each in enumerate(cmd):
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.union(ele_1, ele_2)
        elif cmd == 1:
            if case.same(ele_1, ele_2):
                print('1')
            else:
                print('0')
    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    ele_num, cmd_num = map(int, _input[0].split())
    cmd_list = map(lambda x: x.split(), _input[1:])

    case = UnionFind(size=ele_num)

    ans = action(cmd_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""


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

output:
0
0
1
1
1
0
1
1

"""

import sys


class UnionFind(object):
    __slots__ = ('size', 'tree_height_rank_list', 'ancestor_list')

    def __init__(self, size):
        self.size = int(size)
        self.tree_height_rank_list = [0] * self.size
        self.ancestor_list = [i for i in range(self.size)]

    def _find(self, x):
        if x != self.ancestor_list[x]:
            self.ancestor_list[x] = self._find(self.ancestor_list[x])
        return self.ancestor_list[x]

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

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

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


def action(cmd):
    for _, each in enumerate(cmd):
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.union(ele_1, ele_2)
        elif cmd == 1:
            if case.same(ele_1, ele_2):
                print('1')
            else:
                print('0')
    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    ele_num, cmd_num = map(int, _input[0].split())
    cmd_list = map(lambda x: x.split(), _input[1:])

    case = UnionFind(size=ele_num)

    ans = action(cmd_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""


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

output:
0
0
1
1
1
0
1
1

"""

import sys


class UnionFind(object):
    __slots__ = ('size', 'tree_height_rank_list', 'ancestor_list')

    def __init__(self, size):
        self.size = int(size)
        self.tree_height_rank_list = [0] * self.size
        self.ancestor_list = [i for i in range(self.size)]

    def _find(self, x):
        if x != self.ancestor_list[x]:
            self.ancestor_list[x] = self._find(self.ancestor_list[x])
        return self.ancestor_list[x]

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

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

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


def action(_cmd_list):
    for _, each in enumerate(_cmd_list):
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.union(ele_1, ele_2)
        elif cmd == 1:
            if case.same(ele_1, ele_2):
                print('1')
            else:
                print('0')
    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    ele_num, cmd_num = map(int, _input[0].split())
    cmd_list = map(lambda x: x.split(), _input[1:])

    case = UnionFind(size=ele_num)

    ans = action(cmd_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""


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

output:
0
0
1
1
1
0
1
1

"""

import sys


class UnionFind(object):
    __slots__ = ('size', 'tree_height_rank_list', 'ancestor_list')

    def __init__(self, size):
        self.size = int(size)
        self.tree_height_rank_list = [0] * self.size
        self.ancestor_list = [i for i in range(self.size)]

    def _find(self, x):
        if x != self.ancestor_list[x]:
            self.ancestor_list[x] = self._find(self.ancestor_list[x])
        return self.ancestor_list[x]

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

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

    def union(self, x, y):
        self._link(self._find(x), self._find(y))


def action(_cmd_list):
    for _, each in enumerate(_cmd_list):
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.union(ele_1, ele_2)
        elif cmd == 1:
            if case.same(ele_1, ele_2):
                print('1')
            else:
                print('0')
    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    ele_num, cmd_num = map(int, _input[0].split())
    cmd_list = map(lambda x: x.split(), _input[1:])

    case = UnionFind(size=ele_num)

    ans = action(cmd_list)

Submission status: Accepted

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=="0":
		union.unite(a,b)
	else:
		if union.same(a,b):
			print(1)
		else:
			print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""


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

output:
0
0
1
1
1
0
1
1

"""

import sys


class UnionFind(object):
    __slots__ = ('size', 'tree_height_rank_list', 'ancestor_list')

    def __init__(self, size):
        self.size = int(size)
        self.tree_height_rank_list = [0] * self.size
        self.ancestor_list = [i for i in range(self.size)]

    def __find(self, x):
        if x != self.ancestor_list[x]:
            self.ancestor_list[x] = self.__find(self.ancestor_list[x])
        return self.ancestor_list[x]

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

    def __link(self, x, y):
        if self.tree_height_rank_list[x] > self.tree_height_rank_list[y]:
            self.ancestor_list[y] = x
        else:
            self.ancestor_list[x] = y
            if self.tree_height_rank_list[x] == self.tree_height_rank_list[y]:
                self.tree_height_rank_list[y] += 1

    def union(self, x, y):
        self.__link(self.__find(x), self.__find(y))


def action(cmd_list):
    for each in cmd_list:
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.union(ele_1, ele_2)
        elif cmd == 1:
            if case.same(ele_1, ele_2):
                print('1')
            else:
                print('0')
    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    e_num, c_num = map(int, _input[0].split())
    c_list = map(lambda x: x.split(), _input[1:])

    case = UnionFind(size=e_num)

    ans = action(c_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""


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

output:
0
0
1
1
1
0
1
1

"""

import sys


class UnionFind(object):
    __slots__ = ('size', 'height_rank', 'ancestors')

    def __init__(self, size):
        self.size = int(size)
        self.height_rank = [0] * self.size
        self.ancestors = [i for i in range(self.size)]

    def __find(self, x):
        if x != self.ancestors[x]:
            self.ancestors[x] = self.__find(self.ancestors[x])
        return self.ancestors[x]

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

    def __link(self, x, y):
        if self.height_rank[x] > self.height_rank[y]:
            self.ancestors[y] = x
        else:
            self.ancestors[x] = y
            if self.height_rank[x] == self.height_rank[y]:
                self.height_rank[y] += 1

    def union(self, x, y):
        self.__link(self.__find(x), self.__find(y))


def action(cmd_list):
    for each in cmd_list:
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.union(ele_1, ele_2)
        elif cmd == 1:
            print(int(case.same(ele_1, ele_2)))
    return case


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    e_num, c_num = map(int, _input[0].split())
    c_list = map(lambda x: x.split(), _input[1:])

    case = UnionFind(size=e_num)

    ans = action(c_list)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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

output:
0
0
1
1
1
0
1
1
"""

import sys


class UnionFind(object):
    __slots__ = ('size', 'height_rank', 'ancestors')

    def __init__(self, size):
        self.size = int(size)
        self.height_rank = [0] * self.size
        self.ancestors = [i for i in range(self.size)]

    def __find(self, x):
        if x != self.ancestors[x]:
            self.ancestors[x] = self.__find(self.ancestors[x])
        return self.ancestors[x]

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

    def __link(self, x, y):
        if self.height_rank[x] > self.height_rank[y]:
            self.ancestors[y] = x
        else:
            self.ancestors[x] = y
            if self.height_rank[x] == self.height_rank[y]:
                self.height_rank[y] += 1

    def union(self, x, y):
        self.__link(self.__find(x), self.__find(y))


def cmd_exec(cmd_list, e_num):
    case = UnionFind(size=e_num)

    for each in cmd_list:
        cmd, ele_1, ele_2 = map(int, each)
        if cmd == 0:
            case.union(ele_1, ele_2)
        elif cmd == 1:
            print(int(case.same(ele_1, ele_2)))
    return None


def solve():
    _input = sys.stdin.readlines()
    e_num, c_num = map(int, _input[0].split())
    c_list = map(lambda x: x.split(), _input[1:])

    cmd_exec(c_list, e_num)

    return None


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, n):
        self.p = [x for x in range(n)]
        self.rank = [0 for x in range(n)]

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

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

    def union(self, 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))

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

S = DisjointSet(n)

for i in range(q):
    com, x, y = list(map(int, input().split()))
    if com == 0:
        S.union(x, y)
    elif com == 1:
        if S.same(x, y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
# class UnionFind:
#
#     def __init__(self,n):
#         self.roots = range(n)
#
#     def

def root(i):
    if par[i] == i:
        return i

    par[i]=root(par[i])
    return par[i]

def unite(x,y):
    xr = root(x)
    yr = root(y)
    par[yr] = xr

def same(x,y):
    return root(x)==root(y)



n,q = map(int,input().split())

par = list(range(n))

for i in range(q):
    commands = list(map(int,input().split()))
    if commands[0] == 0:
        unite(commands[1], commands[2])
    if commands[0] == 1:
        if same(commands[1], commands[2]):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class Node:
    def __init__(self):
        self.par = self
        self.rank = 1

class Utree:
    def __init__(self, n):
        self.nodes = [Node() for i in range(n)]

    def root(self, x):
        if x.par is x:
            return x
        else:
            r = self.root(x.par)
            x.par = r
            return r

    def unite(self, x, y):
        xr = self.root(self.nodes[x])
        yr = self.root(self.nodes[y])
        if xr.rank < yr.rank:
            xr.par = yr
            yr.rank += xr.rank
        else:
            yr.par = xr
            xr.rank += yr.rank


    def same(self, x, y):
        return self.root(self.nodes[x]) is self.root(self.nodes[y])



(n, q) = map(int, input().split())
ut = Utree(n)
for i in range(q):
    (c, x, y) = map(int, input().split())
    if c==0:
        ut.unite(x, y)
    else:
        print(1 if ut.same(x, y) else 0)

Submission status: Accepted

Solution code:
# coding: utf-8
class UnionFind:
    def __init__(self, node_num):
        self._rank = [0] * node_num
        self._par  = [i for i in range(node_num)]
        self.N    =  node_num

    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 merge(self, x, y):
        x = self._find(x)
        y = self._find(y)
        if x == y: return

        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[y] += 1

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


N, Q = map(int, input().split())
uf = UnionFind(N)
for _ in range(Q):
    C, X, Y = map(int, input().split())

    if C == 0:
        uf.merge(X, Y)
    else:
        print(1 if uf.is_same(X, Y) else 0)

Submission status: Accepted

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[rootx] = rooty
        else:
            rt[rooty] = rootx
            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: Accepted

Solution code:
import sys

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

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


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 self.root[x] == x:
            return x

        res = self.root[x]
        updates = [x]

        while res != self.root[res]:
            updates.append(res)
            res = self.root[res]

        for u in updates:
            self.root[u] = res

        return res

    def 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)

        if p == q:
            return None

        if self.rank[p] < self.rank[q]:
            self.root[p] = q
        elif self.rank[q] < self.rank[p]:
            self.root[q] = p
        else:
            self.root[q] = p
            self.rank[p] += 1

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: Accepted

Solution code:
import sys

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

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

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


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

        if p == q:
            return None

        if self.rank[p] < self.rank[q]:
            self.root[p] = q
        elif self.rank[q] < self.rank[p]:
            self.root[q] = p
        else:
            self.root[q] = p
            self.rank[p] += 1

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()