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

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
            
    n,q = LI()
    rank = [0]*n
    par = [i for i in range(n)]
    for _ in range(q):
        c,x,y = LI()
        x -= 1
        y -= 1
        if not c:
            if root(x) != root(y):
                unite(x,y)
        else:
            print([0,1][root(x) == root(y)])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


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 = 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())
uf = UnionFind(n)
for _ in range(q):
    com, x, y = map(int,input().split())
    if com == 0:
        uf.union(x, y)
    else:
        if uf.same(x, y):
            print(1)
        else:
            print(0)

Solution (Python):
class UnionFindTree():
    def __init__(self, n):
        
        self.par = list(range(n))

    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 unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        
        self.par[y] = x

    def same(self, x, y):
        
        
        
        print(1) if self.root(x) == self.root(y) else print(0)

def querying(queries, uft):
    for query in queries:
        if query[0] == 0:
            uft.unite(query[1], query[2])
        else:
            uft.same(query[1], query[2])
        
if __name__ == '__main__':
    n, q = map(int, input().split())
    queries = [list(map(int, input().split())) for i in range(q)]
    
    uft = UnionFindTree(n)
    
    querying(queries, uft)

Solution (Python):
import sys,queue,math as np
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
LI = lambda : [int(x) for x in input().split()]

N,Q = LI()
g = [i for i in range(N)]

def root(x):
    if x == g[x] : return x
    g[x] = root(g[x])
    return g[x]

for _ in range(Q):
    c,x,y = LI()
    if c == 0:
        g[root(x)] = root(y)
    else:
        print (int(root(x) == root(y)))

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

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

    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

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

sets = UnionFind(n)
for _ in range(q):
    l = list(map(int, input().split()))
    if l[0] == 0:
        sets.union(l[1], l[2])
    else:
        if(sets.same(l[1], l[2])):
            print(1)
        else:
            print(0)

Solution (Python):
class Unionfind():

    def __init__(self, n):
        self.par = [-1]*n

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.par[x]>self.par[y]:
            x,y = y,x
        self.par[x]+=self.par[y]
        self.par[y] = x
        return True

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

    def count_group():
        c = 0
        for i in range(len(self.par)):
            if self.par[i]<0:
                c+=1
        return c

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

Solution (Python):
class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -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]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			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)] * (-1)


N, Q = map(int, input().split())
solve = UnionFind(N)
ans = []
for _ in range(Q):
	q,x,y = map(int, input().split())
	if q == 0:
		solve.Unite(x,y)
	else:
		ans.append(solve.isSameGroup(x,y))

for a in ans:
	if a:
		print(1)
	else:
		print(0)

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

    def root(self, idx):
        if self.par[idx] == -1:
            return idx

        self.par[idx] = self.root(self.par[idx])
        return self.par[idx]

    def unite(self, idx1, idx2):
        idx1_par = self.root(idx1)
        idx2_par = self.root(idx2)

        if idx1_par == idx2_par:
            return

        if self.size[idx1_par] >= self.size[idx2_par]:
            self.size[idx1_par] += self.size[idx2_par]
            self.par[idx2_par] = idx1_par
        else:
            self.size[idx2_par] += self.size[idx1_par]
            self.par[idx1_par] = idx2_par

    def same(self, idx1, idx2):
        return self.root(idx1) == self.root(idx2)


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

uf = UnionFind(n)

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:  
        uf.unite(x, y)
    else:  
        if uf.same(x, y):
            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 unite(self, x, y):
        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)

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

Solution (Python):
class UnionFind():
  def __init__(self,n):
    self.n = n 
    self.parents = [-1]*n 
  def unite(self,x,y):
    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 find(self,x):
    if self.parents[x] < 0:
      return x
    else:
      
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]
      
      
  def same(self,a,b):
    return self.find(a) == self.find(b)
if __name__ == "__main__":
  n,q = map(int,input().split())
  uf = UnionFind(n)
  for i in range(q):
    com,x,y = map(str,input().split())
    x = int(x)
    y = int(y)
    if com == "0": 
      uf.unite(x,y)
      
    if com == "1": 
      if uf.same(x,y): print(1)
      else: print(0)

Solution (Python):
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
parent=list(range(n))
rank=[0]*n
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]<rank[ry]:
		parent[rx]=ry
	else:
		parent[ry]=rx
		if rank[rx]==rank[ry]:
			rank[rx]+=1
for i in range(q):
	c,a,b=map(int,input().split())
	if c==0:
		unite(a,b)
	else:
		if same(a,b):
			print(1)
		else:
			print(0)

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

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




def find(x):
    if par[x] < 0:
        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 False
    else:
        
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True


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


def size(x):
    return -par[find(x)]


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


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


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


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



par = [-1]*n

"""
uniteでまとめ、findで見つける。
n(要素数)だけ最初に付け加えること。
"""

for i in range(q):
    com,a,b = map(int,readline().split())
    if com:
        if same(a,b):
            print(1)
        else:
            print(0)
    else:
        unite(a,b)

Solution (Python):




class UnionFind:
    __slots__ = ["_size", "_first_index", "_parents"]

    def __init__(self, size: int, is_zero_indexed: bool = True) -> None:
        self._size = size
        self._first_index = 0 if is_zero_indexed else 1
        self._parents = [-1] * (size + self._first_index)

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), 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 get_size(self, x: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]

    @property
    def groups(self) -> int:
        """Return the number of groups."""
        return len({self.find(x) for x in range(self._first_index, self._size + self._first_index)})


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:
            ans.append(uf.is_same(x, y) * 1)
        else:
            uf.unite(x, y)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.size(root_x) < self.size(root_y):
            root_x, root_y = root_y, root_x
        self.parents[root_x] += self.parents[root_y]
        self.parents[root_y] = root_x
        return True

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

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

def main():
    n, q = LI()
    uf = UnionFind(n)
    ans = []
    for _ in range(q):
        com, x, y = LI()
        if com == 0:
            uf.unite(x, y)
        if com == 1:
            if uf.same(x, y):
                ans.append(1)
            else:
                ans.append(0)
    for a in ans:
        print(a)

main()

Solution (Python):
class UnionFind:
    def __init__(self,N):
        self.par =[-1 for i in range(N)]
    def find(self,x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.par[x] > self.par[y]:
            x,y = y,x
        self.par[x] +=self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.find(x)]
    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.unite(x,y)
    else:
        print(int(uf.same(x,y)))

Solution (Python):

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

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

    def unite(self, x, y): 
        
        rx = self.root(x) 
        ry = self.root(y) 
        if (rx == ry): 
            return False

        if (self.rank[rx] > self.rank[ry]): 
            self.parent[ry] = rx
        else:
            self.parent[rx] = ry
            if (self.rank[rx] == self.rank[ry]):
                self.rank[ry] += 1

        return True

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

N, Q = map(int, input().split())
ds = UnionFind(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)

Solution (Python):
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """頂点xを含む集合と頂点y含む集合を結合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """頂点xと頂点yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """頂点xを含む集合の要素数を返す"""
        return -self.parent[self.root(x)]

    def get_cnt(self):
        """集合の個数を返す"""
        return self.cnt


import sys
input = sys.stdin.readline


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

uf = UnionFind(n)
ans = []
for i in range(q):
    t, x, y = info[i]
    if t == 0:
        uf.merge(x, y)
        continue
    if uf.is_same(x, y):
        print(1)
    else:
        print(0)

Solution (Python):
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)]
    self.n = num
    self.size = [1]*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 union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return 
    if self.rank[x] > self.rank[y]:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.size[y] = 0
    else:
      self.par[x] = y
      self.size[y] += self.size[x]
      self.size[x] = 0
      if self.rank[x] == self.rank[y]:
        self.rank[y] += 1
    
  def same(self, x, y):
    return self.find(x) == self.find(y)
  
  def all_find(self):
    ls = []
    for i in range(len(self.par)):
      ls.append(self.find(i))
    return ls
    
n, q = map(int, input().split())

uf = UnionFind(n)

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

  if com == 0:
    uf.union(x, y)
  else:
    print(int(uf.same(x,y)))

Solution (Python):


import sys
iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, Q = iim()

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

    def find(i):
        x = S[i]
        while True:
            k = S[i][0]
            if k == i:
                x[0] = i
                return i
            S[i] = x
            i = k
    def union(i, j):
        ai = find(i)
        aj = find(j)
        if ai != aj:
            S[aj][0] = S[ai][0]
            S[aj] = S[ai]

    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj

    ans = []
    for com, x, y in (map(int, line.split()) for line in sys.stdin):

        if com == 0:
            union(x, y)
            
        elif com == 1:
            ans.append(1 if same(x, y) else 0)
        else:
            raise 1
    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()

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

class UnionFind():
    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_root = self.Find_Root(x)
        y_root = self.Find_Root(y)

        if(x_root == y_root):
            return
        
        if self.rank[x_root] >= self.rank[y_root]:
            self.rank[x_root] += self.rank[y_root]
            self.root[y_root] = x_root
        else:
            self.rank[y_root] += self.rank[x_root]
            self.root[x_root] = y_root

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

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

tree = UnionFind(n)

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        tree.Unite(x, y)
    else:
        is_same = tree.isSameGroup(x, y)
        print(1 if is_same else 0)

Solution (Python):
from collections import deque

class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.member_num = [1 for _ in range(size)]
 
    
    
    def find(self,x):
        Q = deque()
        while self.table[x] >= 0:
            Q.append(x)
            x = self.table[x]
        while len(Q)>0:
            y = Q.pop()
            self.table[y] = x
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        m1=self.member_num[s1]
        m2=self.member_num[s2]
        if s1 != s2:
            if m1 != m2:
                if m1 < m2:
                    self.table[s1] = s2
                    self.member_num[s2]=m1+m2
                    return [m1,m2]
                else:
                    self.table[s2] = s1
                    self.member_num[s1]=m1+m2
                    return [m1,m2]
            else:
                self.table[s1] = -1
                self.table[s2] = s1
                self.member_num[s1] = m1+m2
                return [m1,m2]
        return [0,0]

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

UF = UnionFind(N)

for i in range(Q):
    c,a,b = list(map(int,input().split()))
    
    if c==0:
        UF.union(a,b)
    else:
        if UF.find(a)==UF.find(b):
            print(1)
        else:
            print(0)

Solution (Python):
class UnionFindWithRank(object):
    par = []
    rank = []
    cache = True
    log = []

    def __init__(self, n):
        for i in range(n):
            self.par.append(i)
            self.rank.append(0)

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

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

    def unite(self, x, y):
        ox, oy = x, y
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            x, y = y, x
            self.par[y] = x

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

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

Solution (Python):

'''
所要時間は、分位であった。
'''




import sys





def main():
    n, q = map(int, input().split())
    P = [i for i in range(n)]
    for line in sys.stdin:
        order = line.strip("\n").split()
        x,y = map(int, order[1:])
        if x > y: x, y = y, x
        while(1):
            x = P[x]
            if x == P[x]: break
        while(1):
            y = P[y]
            if y == P[y]: break
        if order[0] == "0": 
            P[x] = P[y] 
        elif order[0] == "1": 
            print(1) if y == x else print(0)
    


    
if __name__ == '__main__':
    main()

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

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self,x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y):
        xroot,yroot = self.find(x),self.find(y)
        if xroot == yroot:
            return
        xrank,yrank = self.rank[xroot],self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
        else:
            self.parents[yroot] = xroot

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.find(x)==uf.find(y) else 0)

Solution (Python):
def main():
    n, q = input().split()
    n = int(n)
    q = int(q)
    nums = [i for i in range(n)]
    rank = [0 for i in range(n)]

    def find_top(x):
        if (nums[x] != x):
            nums[x] = find_top(nums[x])
        return nums[x]

    def unite(x, y):
        x = find_top(x)
        y = find_top(y)
        if rank[x] > rank[y]:
            nums[y] = x
        else:
            nums[x] = y
            if (rank[x] == rank[y]):
                rank[y] += 1

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

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


if __name__ == "__main__":
    main()

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

  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 unite(self, x, y):
    x = self.root(x)
    y = self.root(y)
    self.par[y] = x

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

N, Q = map(int, input().split())
uf = UnionFind(N)

for q in range(Q):
  c, x, y = map(int, input().split())
  if c:
    print(int(uf.same(x, y)))
  else:
    uf.unite(x, y)

Solution (Python):
class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = n
        self.PAR = [ i for i in range(n)]
        self.RANK= [ 0 ] * n

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

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

N,Q  = map(int,input().split())
Ans = []
tree = UnionFind(N+1)
for _ in range(Q):
    t,u,v = map(int,input().split())
    if t == 0:
        tree.union(u,v)
    else:
        if tree.same(u,v):
            Ans.append(1)
        else:
            Ans.append(0)
for a in Ans:
    print(a)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

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

	def root(self, x):
		if self.par[x] == x: return x
		self.par[x] = self.root(self.par[x])
		return self.par[x]
	
	def same(self, x, y):
		return 1 if self.root(x) == self.root(y) else 0
	
	def union(self, x, y):
		x, y = self.root(x), self.root(y)
		if x==y: return

		self.par[x] = y

n, q = MAP()
uf = UnionFind(n)
for _ in range(q):
	com, x, y = MAP()
	if com==0: uf.union(x, y)
	if com==1: print(uf.same(x, y))

Solution (Python):




class Node:
    def __init__(self, num):
        self.num = num
        self.parent = self
        self.rank = 0
    
def findSet(node):
    tmp = []
    while node.parent != node:
        tmp.append(node)
        node = node.parent
    
    while tmp:
        tmp.pop().parent = node
    return node

def unite(x, y):
    node1 = findSet(nodes[x])
    node2 = findSet(nodes[y])
    if node1.rank == node2.rank:
        node2.parent = node1
        node1.rank += 1
    elif node1.rank > node2.rank:
        node2.parent = node1
    else:
        node1.parent = node2

def same(x, y):
    node1 = findSet(nodes[x])
    node2 = findSet(nodes[y])
    return node1.parent == node2.parent

nums=list(map(int,input().split()))
n = nums[0]
q = nums[1]

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

for i in range(q):
    nums=list(map(int,input().split()))
    if nums[0] == 0:
        unite(nums[1], nums[2])
    else:
        if same(nums[1], nums[2]):
            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 = 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):
    x = self.find(x)
    y = self.find(y)

    print(1 if x == y else 0)

  
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)
  else:
    uf.same(x, y)