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):
import sys
input = sys.stdin.readline

class UnionFind:
	def __init__(self, n):
		self.rank = [0] * n
		self.parent = [0] * n
		self.make(n)

	def make(self, n):
		for i in range(n):
			self.parent[i] = i

	def unite(self, x, y):
		xroot = self.findset(x)
		yroot = self.findset(y)
		if self.rank[xroot] < self.rank[yroot]:
			self.parent[xroot] = yroot
		elif self.rank[xroot] > self.rank[yroot]:
			self.parent[yroot] = xroot
		else:
			self.parent[xroot] = yroot
			self.rank[yroot] += 1
			node = y
			while True:
				self.rank[node] += 1
				if self.parent[node] == node:
					break
				node = self.parent[node]
			self.rank[y] += 1

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

def main():
	n, q = map(int, input().strip().split())
	uf = UnionFind(n)
	for i in range(q):
		com, x, y = map(int, input().strip().split())
		if com == 0:
			uf.unite(x, y)
		else:
			xroot = uf.findset(x)
			yroot = uf.findset(y)
			
			if xroot == yroot:
				print("1")
			else:
				print("0")

if __name__ == '__main__':
	main()

Solution (Python):
class unionfind:
  def __init__(self, n):
    self.data = [ -1 for i in range(n) ]
    
  def root(self, x):
    if self.data[x] < 0:
      return x
    else:
      self.data[x] = self.root(self.data[x])
      return self.data[x]
    
  def same(self, l, r):
    return self.root(l) == self.root(r)
  
  def join(self, l, r):
    l = self.root(l)
    r = self.root(r)
    if l == r:
      return False
    if self.data[l] > self.data[r]:
      l, r = r, l
    self.data[l] += self.data[r]
    self.data[r] = l
    return True
  
n,q,*l = map(int,open(0).read().split())
uf = unionfind(n)
for c,x,y in zip(*[iter(l)]*3):
  if c:
    print(int(uf.same(x,y)))
  else:
    uf.join(x,y)

Solution (Python):

class DisjointSet:

    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

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

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

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

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

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

    ds = DisjointSet(n)

    for _ in range(q):
        c, a, b = map(int, input().split(' '))
        
        if c == 0:
            ds.unite(a, b)
        else:
            if ds.same(a, b):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    main()

Solution (Python):
import sys


class UnionFindTree:
    def __init__(self, n_node):
        self.parent = [i for i in range(n_node)]
        self.rank = [0] * n_node

    def find(self, x):
        if self.parent[x] != x:
            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 x != 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 have_same_root(self, x, y):
        return self.find(x) == self.find(y)


if __name__ == "__main__":
    n_node, n_command = map(int, input().split())
    uf_tree = UnionFindTree(n_node)

    for command, x, y in (map(int, i.split()) for i in sys.stdin):
        if command == 0:
            uf_tree.unite(x, y)
        else:
            print(int(uf_tree.have_same_root(x, y)))

Solution (Python):







class UnionFind:
    def __init__(self, N):
        self.N = N  
        
        self.parent = [-1] * N  
        

    def root(self, A):  
        
        
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  
        return self.parent[A]

    def size(self, A):  
        
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        
        
        A = self.root(A)
        B = self.root(B)

        
        if (A == B):
            return False

        
        if (self.size(A) < self.size(B)):
            A, B = B, A

        
        self.parent[A] += self.parent[B]  
        self.parent[B] = A  

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


N, Q = list(map(int, input().split()))
ds = UnionFind(N)
for q in range(Q):
    com, x, y = list(map(int, input().split()))
    if com == 0:
        
        ds.unite(x, y)
    elif com == 1:
        
        print(1 if ds.is_in_same(x, y) else 0)

Solution (Python):

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


class Dset:
    def __init__(self, value):
        self.value = value
        self.rank = 0
        self.parent = self

    def unite(self, y):
        x = self
        while x.parent != x:
            x = x.parent
        while y.parent != y:
            y = y.parent

        if x.rank >= y.rank:
            big = x
            small = y
        else:
            big = y
            small = x

        small.parent = big.parent
        small.rank += 1
        return

    def same(self, y):
        x = self
        while x.parent != x:
            x = x.parent
        while y.parent != y:
            y = y.parent
        if x.parent == y.parent:
            return 1
        else:
            return 0


l = [] * n
for i in range(n):
    l.append(Dset(i))

for i in range(q):
    com, x, y = map(int, sys.stdin.readline().strip().split())
    if com == 0:
        l[x].unite(l[y])
    else:
        print(l[x].same(l[y]))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

def find(x):
    if p[x] == x:
        return x
    else:
        p[x] = find(p[x])
        return p[x]

def unite(x, y):
    px, py = find(x), find(y)
    p[px] = py

n, q = map(int, input().split())
p = list(range(n))
for _ in range(q):
    c, x, y = map(int, input().split())
    if c == 0:
        unite(x, y)
    else:
        print(1 if find(x) == find(y) else 0)

Solution (Python):
from typing import List

class UnionFind:
	def __init__(self, V: int) -> None:
		self.V: int = V
		self.pi: List[int] = [i for i in range(V)]
		self.rank: int = [0 for _ in range(V)]

	def findSet(self, x: int) -> int:
		if x != self.pi[x]:
			self.pi[x] = self.findSet(self.pi[x])
		return self.pi[x]

	def same(self, x: int, y: int) -> bool:
		return self.findSet(x) == self.findSet(y)

	def link(self, x: int, y: int) -> None:
		if self.rank[x] > self.rank[y]:
			self.pi[y] = x
		else:
			self.pi[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def unite(self, x: int, y: int) -> None:
		self.link(self.findSet(x), self.findSet(y))


if __name__ == "__main__":
	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:
			if UF.same(x, y):
				print(1)
			else:
				print(0)

Solution (Python):
import sys
input = sys.stdin.readline

class UnionFindTree:
    def __init__(self, n: int):
        self.n = n
        self.root = [-1] * (n+1)
        self.rank = [0] * (n+1)
    def findRoot(self, x: int) -> int:
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.findRoot(self.root[x])
            return self.root[x]
    def unite(self, x: int, y: int):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    def same(self, x: int, y: int) -> bool:
        if self.findRoot(x) == self.findRoot(y):
            return True
        else:
            return False
    def count(self, x: int) -> int:
        return -self.root[self.findRoot(x)]


def main():
    n, q = map(int, input().split())
    UFT = UnionFindTree(n-1)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            UFT.unite(x, y)
        else:
            if UFT.same(x, y):
                print(1)
            else:
                print(0)


if __name__ == '__main__': main()

Solution (Python):
class UnionFindTree:
  def __init__(self, n: int):
    self.__parent = [i for i in range(n)]
    self.__rank = [0 for i in range(n)]

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

  def __find_set(self, x):
    if x != self.__parent[x]:
      self.__parent[x] = self.__find_set(self.__parent[x])
    return self.__parent[x]

  def __link(self, x, y):
    if self.__rank[x] < self.__rank[y]:
      self.__parent[x] = y
    else:
      if self.__rank[x] == self.__rank[y]:
        self.__rank[x] += 1
      self.__parent[y] = x


N, Q = map(int, input().split())
t = UnionFindTree(N)
for i in range(Q):
  command, x, y = map(int, input().split())
  if command == 0:
    t.unite(x, y)
  if command == 1:
    if t.same(x, y):
      print(1)
    else:
      print(0)

Solution (Python):



import sys

line = input()
n, q = list(map(int, line.split()))
rel = {}
for i in range(0, n):
    rel[i] = []
parent = [i for i in range(0, n)]

def find(x):
    if parent[x] == x:
        return x
    else:
        y = find(parent[x])
        parent[x] = y
        return y

def unite(x, y):
    rx = find(x)
    ry = find(y)
    if rx < ry:
        parent[ry] = rx
    else:
        parent[rx] = ry

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

for _ in range(0, q):
    line = input()
    query, x, y = list(map(int, line.split()))
    if query == 0:
        unite(x, y)
    elif query == 1:
        print(1 if same(x, y) else 0)

Solution (Python):

def init(N, parent, rank):
    for i in range(N):
        parent.append(i)
        rank.append(0)
    return parent, rank

def find(parent, v):
    if parent[v] == v:
        return v
    else:
        parent[v] = find(parent, parent[v])
        return parent[v]

def unite(parent, rank, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a == b:
        return 
    elif rank[a] < rank[b]:
        parent[a] = b
        return parent
    elif rank[a] > b:
        parent[b] = a
        return parent
    else:
        parent[b] = a
        rank[a] += 1
        return parent, rank

def union_find():
    N, Q = [int(i) for i in input().split()]
    parent = []
    rank = []
    init(N, parent, rank)
    for i in range(Q):
        P, A, B = [int(i) for i in input().split()]
        if P == 0:
            unite(parent, rank, A, B)
        else:
            a = find(parent, A)
            b = find(parent, B)
            if a == b:
                print("1")
            else:
                print("0")

if __name__ == "__main__":
    union_find()

Solution (Python):
import sys
input = sys.stdin.readline

def same(node_a, node_b):
    if node_a.root() == node_b.root():
        return True
    else:
        return False

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

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

    nodes = [Node() for i in range(n)]

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

if __name__ == "__main__":
    main()

Solution (Python):
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rank = [0]*(n+1)

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			return 0
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1

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

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

def solve():
	n,q,*l = map(int,open(0).read().split())
	uf = UnionFind(n)
	for c,x,y in zip(*[iter(l)]*3):
		if c:
			print(0 + uf.isSame(x,y))
		else:
			uf.unite(x,y)
            
if __name__=="__main__":
	solve()

Solution (Python):
class Union_find():
    def __init__(self, N):
        self.Group = [i for i in range(N)]
        
    def find(self,x):
        while self.Group[x] != x:
            x = self.Group[x]
        return x

    def Union(self,x,y):  
        if self.find(x) != self.find(y):
            self.Group[self.find(y)] = self.Group[self.find(x)] = min(self.find(y),self.find(x))
    
    
N,q = map(int,input().split())
A = Union_find(N)

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

    if com == 0:
        A.Union(x,y)

    else:
        if A.find(x) == A.find(y):
            print(1)
        else:
            print(0)

Solution (Python):
n,q = map(int, input().split( ))
tag = [i for i in range(n)]
for _ in range(q):
    cmmd,x,y =map(int, input().split( ))
    if cmmd == 0:
        chng1 = []
        chng2 = []
        chng1.append(x)
        x = tag[x]
        chng2.append(y)
        y = tag[y]
        while x != tag[x]:
            chng1.append(x)
            x = tag[x]
        chng1.append(x)
        while y != tag[y]:
            chng2.append(y)
            y = tag[y]
        chng2.append(y)
        if x != y:
            if len(chng1) < len(chng2):
                for x_ in chng1:
                    tag[x_] = y
            else:
                for y_ in chng2:
                    tag[y_] = x
 
    else:
        while x != tag[x]:
            x = tag[x]
        while y != tag[y]:
            y = tag[y]
        if x != y:
            print(0)
        else:
            print(1)

Solution (Python):
class UnionSet:
    def __init__(self, nmax: int) -> None:
        self.size = [1] * nmax
        self.id = [i for i in range(nmax)]

    def root(self, i: int) -> int:
        while (i != self.id[i]):
            self.id[i] = self.id[self.id[i]]
            i = self.id[i]
        return i

    def connected(self, p: int, q: int) -> bool:
        return self.root(p) == self.root(q)

    def unite(self, p: int, q: int) -> None:
        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]


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

    u = UnionSet(n)
    for _ in range(q):
        op, x, y = map(lambda x: int(x), input().split())
        if (0 == op):
            u.unite(x, y)
        else:
            print(f"{1 if u.connected(x, y) else 0}")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

class Union_find:
    
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rank=[0]*(n+1)

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

    def unite(self,x,y):
        x=self.find_root(x)
        y=self.find_root(y)

        if x==y:
            return 
        elif self.rank[x]>self.rank[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

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

    def count(self,x):
        return -self.root[self.find_root(x)]

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

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

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

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

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

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


def main():
    n, q = map(int, input().split())
    ds = DisjointSet(n)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            ds.unite(x, y)
        elif com == 1:
            print(1 if ds.same(x, y) else 0)


if __name__ == '__main__':
    main()

Solution (Python):
class Node:
    def __init__(self, data):
        self.data = data
        self.parent = self

def find_root(node):
    if node.parent == node:
        return node

    else:
        node.parent = find_root(node.parent)
        return node.parent

def unite(x, y):
    x_root = find_root(x)
    y_root = find_root(y)
    if x_root == y_root:
        return
    else:
        y_root.parent = x_root

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


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

    nodeset = []
    for i in range(n):
        nodeset.append(Node(i))

    for i in range(q):  
        com, x, y = map(int, input().split())
        x_node = nodeset[x]
        y_node = nodeset[y]
        if com == 0:
            unite(x_node, y_node)
        else:
            same(x_node, y_node)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.root=[-1]*(n+1)
        self.rnk=[0]*(n+1)

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)
        if x==y:
            return
        elif self.rnk[x]>self.rnk[y]:
            self.root[x]+=self.root[y]
            self.root[y]=x
        else:
            self.root[y]+=self.root[x]
            self.root[x]=y
            if self.rnk[x]==self.rnk[y]:
                self.rnk[y]+=1

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

    def Count(self,x):
        return -self.root[self.Find_Root(x)]

n,q=map(int,input().split())
uf=UnionFind(n)
l=[list(map(int,input().split())) for _ in range(q)]
for i in range(q):
    p,x,y=l[i][0],l[i][1],l[i][2]
    if not p:
        uf.Unite(x,y)
    else:
        print(1 if uf.isSameGroup(x,y) else 0)

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)

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.union(x, y)
    elif com == 1:  
        if uf.same_check(x, y):
            print('1')
        else:
            print('0')

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


class UnionFind:
  def __init__(self, size):
    self.size = size
    self.parent = [i for i in range(size)]
    self.size = [1 for _ in range(size)]
    self.height = [1 for _ in range(size)]

  def root(self, i):
    if i != self.parent[i]:
      self.parent[i] = self.root(self.parent[i])
    return self.parent[i]

  def union(self, i, j):
    pi, pj = self.root(i), self.root(j)
    if pi == pj:
      return
    if self.height[pi] < self.height[pj]:
      self.parent[pi] = pj
      self.size[pj] += self.size[pi]
    else:
      self.parent[pj] = pi
      self.size[pi] += self.size[pj]
      if self.height[pi] == self.height[pj]:
        self.height[pi] += 1

  def is_same(self, i, j):
    return self.root(i) == self.root(j)


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


if __name__ == '__main__':
  main()

Solution (Python):
class DisjointSet:
    def __init__(self, size):
        self.rank = [0 for i in range(size)]
        self.p = [0 for i in range(size)]
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

if __name__ == '__main__':
    n, q = map(int, input().split())
    ds = DisjointSet(n)    
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            ds.unite(x, y)
        else:
            if ds.same(x, y):
                print(1)
            else:
                print(0)

Solution (Python):
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_
    def is_group(self,other):
        return self.root()==other.root()
n,q=map(int,input().split())
U=[UnionFindNode(i) for i in range(n)]
for i in range(q):
    com,x,y=map(int,input().split())
    x-=1
    y-=1
    if com==0:
        U[x].unite(U[y])
    else:
        if U[x].is_group(U[y]):
            print(1)
        else:
            print(0)

Solution (Python):
import sys
sys.setrecursionlimit(10000)


class Node:
    
    def __init__(self):
        self.root = self
        self.child = None
        self.length = 1
    
    def set_root(self, root):
        if self.child:
            self.child.set_root(root)
        self.root = root
            
    def set_child(self, child):
        if self.child:
            self.child.set_child(child)
        else:
            self.child = child
        
        
n,q = [int(i) for i in input().split()]
A = []
for i in range(n):
    A.append(Node())

for i in range(q):
    c, x, y = [int(i) for i in input().split()]
    if c == 0:
        if A[x].root == A[y].root:
            continue
        if A[x].root.length < A[y].root.length:
            A[y].set_child(A[x].root)
            A[y].root.length += A[x].root.length
            A[x].root.set_root(A[y].root)
        else:
            A[x].set_child(A[y].root)
            A[x].root.length += A[y].root.length
            A[y].root.set_root(A[x].root)
    else:
        if A[x].root == A[y].root:
            print(1)
        else:
            print(0)

Solution (Python):
def find(x):
    global s
    if s[x] == x:
        return x
    s[x] = find(s[x])
    return s[x]
 
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:
        if find(x) == find(y): print(1)
        else: print(0)
    else:
        s[find(y)] = find(x)

Solution (Python):
n, q = map(int,input().split())
queries = []
for _ in range(q):
    com, x, y = map(int,input().split())
    queries.append((com, x, y))

joining = [[x] for x in range(n)]

def unite(x, y):
    if joining[x] == joining[y]:
        return
    joining[x] += joining[y]
    for member in joining[y]:
        joining[member] = joining[x]

def is_same(x, y):
    return joining[x] == joining[y]

answers = []
for query in queries:
    if query[0] == 0:
        unite(query[1], query[2])
    else:
        answers.append(is_same(query[1], query[2]))

for answer in answers:
    if answer:
        print(1)
    else:
        print(0)

Solution (Python):
def main():
     def root(x):
          path=[]
          while x!=P[x]:
               path.append(x)
               x=P[x]
          for i in path:
               P[i]=x
          return x
     
     def is_same_set(x,y):
          return root(x)==root(y)
     
     def unite(x,y):
          P[root(x)]=root(y)
     
     n,q=map(int,input().split())
     P=[i for i in range(n)]
     for i in range(q):
          q,a,b=map(int,input().split())
          if q==0:
               unite(a,b)
          else:
               if is_same_set(a,b):
                    print(1)
               else:
                    print(0)
     
if __name__=='__main__':
     main()

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

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

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

n,q = map(int,input().split())
P = [i for i in range(n)]
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(' '))

uf = list(range(n))
import sys
sys.setrecursionlimit(30000)
def find_root(x):
    global uf
    if uf[x] == x:
        return x
    else:
        uf[x] = find_root(uf[x])
        return uf[x]

for _ in range(q):
    c, x, y = map(int, input().split(' '))
    if c == 0:
        
        uf[find_root(x)] = find_root(y)
    else:
        
        print(int(find_root(x) == find_root(y)))

Solution (Python):
n,q = map(int,input().split())
L = []
for i in range(q):
    L.append(list(map(int,input().split())))
par = []
for i in range(n):
    par.append(i)
rank = [0]*n
def find(x,par):
    if x == par[x]:
        return x
    else:
        return find(par[x],par)
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    if x != y:
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
for i in range(q):
    if L[i][0] == 0:
        unite(L[i][1],L[i][2],par,rank)
    else:
        if find(L[i][1],par) == find(L[i][2],par):
            print(1)
        else:
            print(0)

Solution (Python):
def root(x):
    path = []
    while P[x] != x:
        path.append(x)
        x = P[x]
    for node in path:
        P[node] = x
    return x
def check(x,y):
    if root(x) == root(y):
        return 1
    else:
        return 0
def unite(x,y):
    P[root(x)] = root(y)        
 
n,q = map(int,input().split())
P = [i for i in range(n)]
for j in range(q):
    s = list(map(int,input().split()))
    if s[0] == 0:
        unite(s[1],s[2])
    else:
        print(check(s[1],s[2]))

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

P = [i for i in range(n)]
def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x
    return x
def is_same_set(x,y):
    if root(x) == root(y):
        return 1
    else: return 0
def unite(x,y):
    P[root(x)] = root(y)

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

Solution (Python):
n,m=map(int,input().split())
p=[i for i in range(n+1)]
def root(n):
  pathroot=[]
  while p[n]!=n:
    pathroot.append(n)
    n=p[n]
  for node in pathroot:
    p[node]=n
  return n
def same(n,m):
  return root(p[n])==root(p[m])
def union(n,m):
  p[root(n)]=root(m)
for i in range(m):
  a,x,y=map(int,input().split())
  if a==1:
    if same(x,y):
      print(1)
    else:
      print(0)
  else:
    union(x,y)