Problem:
Disjoint Set Write a program which manipulates a disjoint set S = {S 1 , S 2 , . . . , S k } . First of all, the program should read an integer n , then make a disjoint set where each element consists of 0, 1, ... n−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 S x and S y , into a new set. same(x, y) : determine whether x and y are in the same set.  Input  n  q  com 1  x 1  y 1  com 2  x 2  y 2 ... com q  x q  y q  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 ≠ 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

Solution (Python):

class DisjointSet():
    def __init__(self, size):
        self.size = size
        self.rank = [None] * size
        self.parents = [None] * size
        for i in range(size):
            self.makeSet(i)

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

    def findSet(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.findSet(self.parents[x])
        return self.parents[x]

    def same(self, x, y):
        return 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.parents[y] = x
        else:
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1


if __name__ == '__main__':

    n, q = [int(s) for s in input().split(" ")]
    com = [list(map(int, input().split(" "))) for _ in range(q)]
    ds = DisjointSet(n)

    for c, x, y in com:
        if c == 0:
            ds.unite(x, y)
        else:
            print(int(ds.same(x, y)))

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

    def unit(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            if self.rank[x] > self.rank[y]:
                self.parent[y] = x
            else:
                self.rank[x] += 1
                self.parent[y] = x


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

Solution (Python):
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[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        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)

Solution (Python):
import sys

def findset(x,element):
    if(x != element[x]):
        element[x] = findset(element[x],element)
    return element[x]

def union(x,y,rank,element):
    link(findset(x,element),findset(y,element),rank,element)

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

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

element = [i for i in range(n)]
rank = [0 for i in range(n)]

for i in range(q):
    query,x,y = map(int, input().split());
    if(query == 0):
        union(x,y,rank,element)
    else :
        if(findset(x,element) == findset(y,element)):
            print(1)
        else:
            print(0)

Solution (Python):
import sys

def findset(x,element):
    if(x != element[x]):
        element[x] = findset(element[x],element)
    return element[x]

def union(x,y,rank,element):
    link(findset(x,element),findset(y,element),rank,element)

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

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

element = [i for i in range(n)]
rank = [0 for i in range(n)]

for i in range(q):
    query,x,y = map(int, input().split());
    if(query == 0):
        union(x,y,rank,element)
    else :
        if(findset(x,element) == findset(y,element)):
            print(1)
        else:
            print(0)

Solution (Python):

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

p = [i for i in range(n)]
rank = [0 for i in range(n)]

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]


def unite(x, y):
 union(x, y)

def same(x, y):
 x = findSet(x)
 y = findSet(y)

 if x == y:
  return 1
 else :
  return 0


output = []

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

 if com == 0:
  unite(x, y)
 else :
  output.append(same(x,y))

for ans in output:
 print(ans)

Solution (Python):

p = []
rank = []

def makeSet(x):
    global p, rank
    p.append(x)
    rank.append(0)

def findSet(x):
    global p
    if x != p[x]:
        p[x] = findSet(p[x])
    return p[x]

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

def union(x, y):
    link(findSet(x), findSet(y))    

def same(x, y):
    if findSet(x) == findSet(y):
        return 1
    else:
        return 0   

[n, q] = list(map(int, input().split()))
for i in range(n):
    makeSet(i)

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

Solution (Python):

def union(x, y):
    link(findSet(x), findSet(y))

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

def findSet(x):
    if x != p[x]:
        p[x] = findSet(p[x])
    return p[x]


if __name__ == '__main__':

    p = [];
    r = [];

    n_set, n_quare = map(int, input().split())

    for i in range(n_set):
        p.append(i)
        r.append(0)


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

        if q == 0:
            union(x, y)

        else:
            print(int(findSet(x) == findSet(y)))

Solution (Python):
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(1)
        else:
            print(0)

Solution (Python):



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 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':
        
        i_x = search(x)
        i_y = search(y)
        if i_x != None and i_y != None and i_x != i_y:
            sets[i_x] = unite(sets[i_x], sets[i_y])
            del sets[i_y]
    elif query == '1':
        
        print(same(x, y))

Solution (Python):



class UnionFindTree():
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(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 same_check(self, x, y):
        return self.find(x) == self.find(y)

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

for i in range(q):
    com, x, y = [int(x) for x in input().split(' ')]
    if com == 0:
        uft.unite(x, y)
    elif com == 1:
        if uft.same_check(x, y):
            print(1)
        else:
            print(0)

Solution (Python):
import sys


class UnionFind:
    def __init__(self, max_size):
        self.max_size = max_size
        self.dat = [i for i in range(self.max_size)]

    def find(self, vertex):
        if self.dat[vertex] is vertex: return vertex
        self.dat[vertex] = self.find(self.dat[vertex])
        
        return self.dat[vertex]

    def merge(self, child, parent):
        """
        parentとchildをマージして、parentの所属にする
        :param parent:
        :param child:
        :return:
        """
        self.dat[self.find(child)] = self.dat[self.find(parent)]

    def is_same(self, v, w):
        """
        頂点vと頂点wが同じ集合に所属しているか
        :param v:
        :param w:
        :return:
        """
        return self.find(v) == self.find(w)


n, q = map(int, input().split())
uni = UnionFind(n)
sys.setrecursionlimit(114514)
while q > 0:
    q -= 1
    com, x, y = map(int, input().split())
    if com is 0:
        uni.merge(x, y)
    else:
        print(1 if uni.is_same(x, y) else 0)

Solution (Python):

class UnionFindTree:

    def __init__(self):
        self.cnt = []
        self.par = []

    def add(self, n):
        assert n == len(self.par), "Invalid Value"
        self.par.append(n)
        self.cnt.append(1)

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            cnt = self.cnt[x] + self.cnt[y]
            self.cnt[x] = cnt
            self.cnt[y] = cnt
            if x < y:
                self.par[y] = x
            else:
                self.par[x] = y

    def size(self, x):
        x = self.root(x)
        return self.cnt[x]


def main():
    n, q = map(int, input().split())
    uf = UnionFindTree()
    for i in range(n):
        uf.add(i)
    for _ 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()

Solution (Python):
import collections
import itertools
import operator
import sys


class UnionFind:
    def __init__(self):
        class KeyDict(dict):
            def __missing__(self, key):
                self[key] = key
                return key

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

    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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1

    def are_same(self, x, y):
        return self.find(x) == self.find(y)

    def grouper(self):
        parent_getter = operator.itemgetter(1)
        for _, group in itertools.groupby(
                sorted(self.parent.items(), key=parent_getter), parent_getter):
            yield [i for i, _ in group]


sys.stdin.readline()
uf = UnionFind()
for line in sys.stdin:
    com, x, y = map(int, line.split())
    if com == 0:
        uf.unite(x, y)
    elif com == 1:
        print(1 if uf.are_same(x, y) else 0)

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


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)


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

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

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

def root(x):
    path_to_root = []
    while root_list[x] != x:
        path_to_root.append(x)
        x = root_list[x]
    for node in path_to_root:
        root_list[node] = x
    return x

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

def unite(x,y):
    root_list[root(x)] = root(y)

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

Solution (Python):
n,q = map(int, input().split())
lines = [list(map(int, input().split())) for i in range(q)]
set = []
c = 0
index = [-i-1 for i in range(n)]
for line in lines:
	if line.pop(0) == 0:
		index_a = index[line[0]]
		index_b = index[line[1]]
		if index_a < 0 and index_b < 0:
			set += [line]
			index[line[0]] = c
			index[line[1]] = c
			c += 1
		elif index_a < 0:
			set[index_b] += [line[0]]
			index[line[0]] = index_b
		elif index_b < 0:
			set[index_a] += [line[1]]
			index[line[1]] = index_a
		elif index_a == index_b:
			continue
		else:
			set[index_a] += set[index_b]
			for i in set[index_b]:
				index[i] = index_a
		
	else:
		if index[line[0]] == index[line[1]]:
			print(1)
		else:
			print(0)

Solution (Python):
n,q = map(int, input().split())
group = [[i] for i in range(n)]
key = [i for i in range(n)]
for j in range(q):
    com, x, y = map(int, input().split())
    if com == 1:
        if key[x] == key[y]:
            print(1)
        else:
            print(0)
    else:
        if key[x] != key[y]:
            v = key[y]
            group[key[x]] += group[v]
            for i in group[v]:
                key[i] = key[x]
            group[v] = []

Solution (Python):




class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]


n, q = map(int, input().split())
u = UnionSet(n)
for i in range(q):
	cmd, x, y = map(int, input().split())
	if cmd == 0: u.unite(x, y)
	else: print(1 if u.connected(x, y) else 0)

Solution (Python):
class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parent = list(range(N))

    def root(self, x):
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  
        return x

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

    def unite(self, x, y):
        self.parent[self.root(x)] = self.root(y)

    def __str__(self):
        groups = {}
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result

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

Solution (Python):
n,m = map(int,raw_input().split())

arr = []

for i in range(n):
	arr.append(i)

def root(i):
	t = i
	while arr[t] != t:
		t = arr[t]

	return t

for i in range(m):
	query,x,y = map(int,raw_input().split())

	if query == 0:
		if root(y) == root(x):
			next 
		else :
			arr[root(y)] = root(x)

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

Solution (Python):
def main():
    n,q = [int(i) for i in input().split()]
    
    par = [ i for i in range(n)]
    
    rank = [ 0 for i in range(n)]
    
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        if rank[x]<rank[y]:
            par[x] = y
            return
        elif rank[y]<rank[x]:
            par[y] = x
            return
        else:
            par[x] = y
            rank[y] +=1
            return

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

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

if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.size   = n
        self.rank   = [0] * n
        self.weight = [1] * 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 same(self, x, y):
        return self.find(x) == self.find(y)
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.weight[y] += self.weight[x]
        else:
            self.parent[y] = x
            self.weight[x] += self.weight[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] = self.rank[x] + 1
            
if __name__ == "__main__":
    n, q = map(int, raw_input().split())

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

Solution (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:
            if x in s[x] and y in s[x]:
                print(1)
            else:
                print(0)
        else:
            a = s[x]
            b = s[y]
            if a is not b:
                a |= b
                for i in a:
                    s[i] = a


main()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    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 union(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 same_check(self, x, y):
        return self.find(x) == self.find(y)

if __name__ == "__main__":
    
    
    n, q = map(int, input().split())
    u = UnionFind(n)

    ans_list = []
    for _ in range(q):
        com, x, y = map(int, input().split())

        if com == 1:
            ans = u.same_check(x, y)
            ans_list.append(ans)
        else:
            u.union(x, y)

    for num in ans_list:
        print(int(num))

Solution (Python):
class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_size(self, x):
        return self.size[self.find(x)]

n, q = map(int, input().split())
uf = UnionFind(n)
for _ 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)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy


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

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        uni.merge(x, y)
    else:
        print(int(uni[x] == uni[y]))

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

buf = [i for i in range(n)]
height = [1] * n

def find(i):
    while i != buf[i]:
        i = buf[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    if height[i] >= height[j]:
        buf[j] = i
        height[i] = max(height[i], height[j] + 1)
    else:
        buf[i] = j
        height[j] = max(height[j], height[i] + 1)

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

Solution (Python):
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(y)

N, Q = map(int, input().split())
uf = UnionFind(N)
for _ in range(Q):
  p, a, b = map(int, input().split())
  if p == 0:
    uf.unite(a, b)
  else:
    if uf.is_same(a, b):
      print(1)
    else:
      print(0)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        xとyは-=1して使う
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,Q = map(int,input().split())
u = UnionFind(n)
ans_ls = []
for i in range(Q):
    q,x,y = map(int,input().split())
    if q == 1:
        if u.same(x,y):
            ans_ls.append(1)
        else:
            ans_ls.append(0)
    else:
        u.union(x,y)
for i in range(len(ans_ls)):
    print(ans_ls[i])

Solution (Python):
import sys

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N))
        self._rank = [0] * self.N
        self._size = [1] * self.N

    def find(self, x):
        if self._parent[x] != x:
            self._parent[x] = self.find(self._parent[x])
        return self._parent[x]

    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

    def same_set(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self._size[self.find(x)]


def main():
    N, Q = map(int, input().split())

    uf = UnionFind(N)

    ans = []
    for _ in range(Q):
        com, x, y = map(int, input().split())
        if com == 0:
            uf.union(x, y)
        else:
            ans.append(int(uf.same_set(x, y)))

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


class UnionFind:
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, N):
        if self.tree[N] == N:
            return N
        else:
            self.tree[N] = self.root(self.tree[N])
            return self.tree[N]

    def same(self, x, y):
        return self.root(self.tree[x]) == self.root(self.tree[y])

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        else:
            self.tree[x] = y


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, Q = il()
    uf = UnionFind(N)
    for q in range(Q):
        com, x, y = il()
        if com == 0:
            uf.unite(x, y)
        else:
            print(1 if uf.same(x, y) else 0)


if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind():
    
    def __init__(self, n):
        self.rank = [0] * n 
        self.par = list(range(n))

    
    def find(self, x):
        children = []
        while self.par[x] != x:
            children.append(x)
            x = self.par[x]

        for c in children:
            self.par[c] = x
        return x

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

    def union(self, x, y):
        if self.same(x, y):
            return
        rx = self.find(x)
        ry = self.find(y)
        if self.rank[rx] > self.rank[ry]:
            self.par[ry] = rx 
        elif self.rank[rx] == self.rank[ry]:
            self.par[ry] = rx
            self.rank[rx] += 1
        else:
            self.par[rx] = ry

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

for _ in range(q):
    cmd, x, y = [int(x) for x in input().split()]
    if cmd == 0: 
        uf.union(x, y)
    else: 
        print(int(uf.same(x, y)))