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,collections,math
sys.setrecursionlimit(1000000)

INF = float("inf")

N,Q = map(int,sys.stdin.readline().split())
COM = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) 

parents = list(range(N))
def find(x):
  while parents[x] != x:
    x = parents[x]
    parents[x] = parents[parents[x]]
  return x
def union(s,t):
  sp = find(s)
  tp = find(t)
  if sp == tp:
    pass
  elif sp < tp:
    parents[sp] = tp
  else:
    parents[tp] = sp

for com,x,y in COM:
    if com == 0:
        union(x,y)
    else:
        if find(x) == find(y):
            print(1)
        else:
            print(0)

Solution (Python):
n, q = map(int, input().split())
com, x, y = [0] * q, [0] * q, [0] * q
for i in range(q):
    com[i], x[i], y[i] = map(int, input().split())


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

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

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

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


for i in range(q):
    if com[i] == 0:
        unite(x[i], y[i])
    else:
        if same(x[i], y[i]):
            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 same(self, x, y):                                       
        return self.find(x) == self.find(y)

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

A = UnionFind(n)

for c,x,y in [list(map(int,input().split())) for _ in range(q)]:
    if not c:
        A.union(x,y)
    else:
        print(int(A.same(x,y)))

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








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


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


def unit(x, y):
    root_x = root(x)
    root_y = root(y)
    if root_x < root_y:
        parents[root_y] = root_x
    else:
        parents[root_x] = root_y


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


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

Solution (Python):
from collections import deque


class UnionFind:
    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


N, Q = map(int, input().split(' '))
queries = [tuple(map(int, input().split(' '))) for _ in range(Q)]
union_find = UnionFind(N - 1)
for p, a, b in queries:
    if p == 0:
        union_find.union(a, b)
    else:
        if union_find.find(a, b):
            print(1)
        else:
            print(0)

Solution (Python):

def search_root(x):
    i = x
    while True:
        if i == nodes[i]:
            nodes[x] = i
            return i
        else:
            i = nodes[i]

def unite(x,y):
    nodes[search_root(x)] = search_root(y)

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


n, q = map(int, input().split())
nodes = [i for i in range(n)]
commands = []
for _ in range(q):
    commands.append(input())
for cmd in commands:
    c,x,y = map(int,cmd.split())
    if c == 0:
        unite(x,y)
    else:
        same(x,y)

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

uft = UnionFind(n)

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

Solution (Python):
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N)]
        self.siz=[1 for _ in range(N)]
        self.rank=[0 for _ in range(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,a,b):
        a=self.find(a)
        b=self.find(b)
        if a==b:
            return 0
        else:
            if self.rank[a]>self.rank[b]:
                self.par[b]=a
                self.siz[a]+=self.siz[b]
            else:
                self.par[a]=b
                self.siz[b]+=self.siz[a]
                if self.rank[a]==self.rank[b]:
                    self.rank[b]+=1
    def size(self,a):
        return self.siz[self.find(a)]
    def same(self,a,b):
        return self.find(a)==self.find(b)

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

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

par = [-1] * n
rank = [0] * n


def find(x):
    """ 根ノードの値を見つけて返す """
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    """xとyを結合する"""
    rootx = find(x)
    rooty = find(y)

    if rootx == rooty:
        return False
    else:
        if rank[rootx] < rank[rooty]:
            par[rootx] = rooty
        else:
            par[rooty] = rootx
            if rank[rootx] == rank[rooty]: rank[rootx] += 1
        return True

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


for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        unite(x, y)
    elif com == 1:
        if 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 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)
ans = []
for _ in range(q):
    com,x,y = map(int,input().split())
    if com == 0:
        uf.union(x,y)
    else:
        judge = uf.same(x,y)
        if judge:
            ans.append(1)
        else:
            ans.append(0)
for i in ans:
    print(i)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {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:
        print(int(uf.same(x, y)))

Solution (Python):
class unionfind:
    sz = 0
    par = []
    def __init__(self, n):
        self.sz = n
        for i in range(n):
            self.par.append(-1)

    def find(self, a):
        if self.par[a]<0: return a
        self.par[a] = self.find(self.par[a])
        return self.par[a]
    
    def size(self, a):
        a = self.find(a)
        return -self.par[a]
    
    def same(self, a,b):
        return self.find(a) == self.find(b)

    def unite(self, a,b):
        a = self.find(a)
        b = self.find(b)
        if self.same(a,b): return False
        if self.size(a) < self.size(b):
            a,b=b,a
        self.par[a] += self.par[b]
        self.par[b] = a
        return True

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

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

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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

def resolve():
    n, q = LI()
    uf = UnionFind(n)
    for _ in range(q):
        comxy = LI()

        com = comxy[0]
        x = comxy[1]
        y = comxy[2]

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

if __name__ == '__main__':
    resolve()

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * 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 unite(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
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False 


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)
    if com == 1:
        print(int(UF.same(x, y)))

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

    def nums(self,x):
        return abs(self.parents[self.find(x)])

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

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

    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 i in range(Q):
    com,x,y = map(int, input().split())
    if com==0:
        uf.union(x,y)
    if com==1:
        print(int(uf.same(x,y)))

Solution (Python):
n,q = map(int,input().split())
commands = [0]*q
args = [[0,0] for _ in range(q)]
for i in range(q):
    tmp = list(map(int,input().split()))
    commands[i] = tmp[0]
    args[i] = tmp[1:3]

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 in range(self.n) if self.parents[i] < 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())

tree = UnionFind(n)

for i in range(q):
    if commands[i] == 0:
        tree.union(args[i][0],args[i][1])
    else:
        if tree.same(args[i][0],args[i][1]):
            print(1)
        else:
            print(0)

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

    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[y] < self.rank[x]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

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)
    if com == 1:
        print(1 if ds.same(x, y) else 0)

Solution (Python):



class UnionFind:

    def __init__(self, size: int):
        
        
        self.size = size
        self.parent = [-1] * size

    def find(self, x: int) -> int:
        """
        xを含む集合の代表を求める
        """
        if self.parent[x] < 0:
            return x
        
        same_group_items = []
        while self.parent[x] >= 0:
            same_group_items.append(x)
            x = self.parent[x]
        for child in same_group_items:
            self.parent[child] = x
        return x

    def unite(self, x: int, y: int):
        """
        xを含む集合とyを含む集合を併合する
        """
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.parent[root_x] >= self.parent[root_y]:
                self.parent[root_x] += self.parent[root_y]
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] += self.parent[root_x]
                self.parent[root_x] = root_y

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


def solve():
    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)


if __name__ == "__main__":
    solve()

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

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

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

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

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

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

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


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

Solution (Python):
class UnionFind():
  def __init__(self, n):
    
    self.parents = list(range(n))
  
  def find(self,x):
    if self.parents[x] == x:
      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:
      self.parents[y] = x

import sys
input = sys.stdin.readline
n, q = map(int,input().split())
uf = UnionFind(n)

for i in range(q):
  com, x, y = map(int, input().split())
  if com:
    print(int(uf.find(x) == uf.find(y)))
  else:
    uf.union(x,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 x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
    def union(self, x, y):
        parx = self.find(x)
        pary = self.find(y)
        if self.rank[parx] < self.rank[pary]:
            self.par[parx] = pary
        else:
            self.par[pary] = parx
            if self.rank[pary] == self.rank[parx]:
                self.rank[parx] += 1
n,q = map(int, input().split())
G = UnionFind(n)
ans = []
for _ in range(q):
    c,x,y = map(int, input().split())
    if c == 0:
        G.union(x,y)
    elif c == 1:
        if G.check(x,y) == True:
            ans.append(1)
        else:
            ans.append(0)
    
    
    

for i in range(len(ans)):
    print(ans[i])

Solution (Python):


from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')


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

parents = [i for i in range(n)]
size = [1 for _ in range(n)]


def find(x):
    if x != parents[x]:
        parents[x] = find(parents[x])
    return parents[x]


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


def unite(x, y):
    x_root = find(x)
    y_root = find(y)
    if x_root == y_root:
        return
    if x_root < y_root:
        x_root, y_root = y_root, x_root
    parents[y_root] = x_root
    size[x_root] += size[y_root]


for com, x, y in queries:
    if com == 0:
        unite(x, y)
    else:
        if 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 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)
ans = []
for _ in range(Q):
    com, x, y = map(int, input().split())
    if com:
        if uf.same(x, y):
            ans.append(1)
        else:
            ans.append(0)
    else:
        uf.union(x, y)
print(*ans, sep='\n')

Solution (Python):
from sys import setrecursionlimit

class UnionFind:
    def __init__(self, n):
        
        
        self.par = [i for i in range(n + 1)]
        
        self.rank = [0] * (n + 1)
        self.size = [1] * (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 check(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
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self):
        return len({self.find(x) for x in range(n)})

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:
        if uf.check(x, y):print(1)
        else:print(0)

Solution (Python):
import sys

readline = sys.stdin.readline

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

def main():
    n, q = map(int, readline().split())
    uf = UnionFind(n)
    for _ in range(q):
        com, x, y = map(int, readline().split())
        if com == 0:
            uf.union(x, y)
        else:
            px = uf.find(x)
            py = uf.find(y)
            print((px == py)*1)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class UnionFind:
    def __init__(self, n):
        
        self.par = [i for i in range(n+1)]
        
        self.size = [1] * (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 x == y:
            return
        
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    
    def get_size(self, x):
        return self.size[self.find(x)]
    
    
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c


def main():
    n,q,*query = map(int, read().split())

    uf = UnionFind(n)

    for com, x, y in zip(*[iter(query)]*3):
        if com:
            print(1 if uf.is_same(x, y) else 0)
        else:
            uf.unite(x, y)


if __name__ == "__main__":
    main()

Solution (Python):
import sys















def main():
    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())
    que = UnionFind(n)

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


if __name__ == '__main__':
    main()