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

for _ in range(q):
    com,x,y=map(int,input().split())
    if com:
        print(int(root(x)==root(y)))
    else:
        p[root(x)]=root(y)

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

    def __init__(self, dimension):
        self.root = [i for i in range(dimension)]
        self.height = [1 for i in range(dimension)]

    def parent(self, i):
        p = self.root[i]
        if i == p:
            return p
        else:
            pp = self.parent(p)
            self.root[i] = pp
            return pp

    def unite(self, i1, i2):
        p1 = self.parent(i1)
        p2 = self.parent(i2)
        if self.height[p1] < self.height[p2]:
            self.root[p1] = p2
        else:
            self.root[p2] = p1
            if self.height[p1] == self.height[p2]:
                self.height[p1] += 1

    def same(self, i1, i2):
        return self.parent(i1) == self.parent(i2)


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

Solution (Python):
class UnionFind:
    def __init__(self, N):
        
        
        self.vertices = [-1 for _ in range(N)]
        self.rank = [0] * N
        
    def find(self, v):
        if self.vertices[v] < 0: 
            return v
        else:
            
            self.vertices[v] = self.find(self.vertices[v])
            return self.vertices[v]
        
    def union(self, u, v):
        s1 = self.find(u) 
        s2 = self.find(v) 
        
        if s1 == s2: 
            return False
        
        if self.rank[s1] > self.rank[s2]: 
            self.vertices[s1] += self.vertices[s2] 
            self.vertices[s2] = s1
        else: 
            self.vertices[s2] += self.vertices[s1] 
            self.vertices[s1] = s2
            if self.rank[s1] == self.rank[s2]:
                self.rank[s2] += 1
        return True
        
    def is_connected(self, u, v):
        return self.find(u) == self.find(v)
    
    def size(self, v):
        return -self.vertices[self.find(v)]

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

Solution (Python):


from collections import deque
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

par = [i for i in range(n + 1)]
rnk = [0 for i in range(n + 1)]

def find(x):
    if par[x] == x:
        return x
    par[x] = find(par[x])
    return par[x]

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

def unite(x, y):
    x_par = find(x)
    y_par = find(y)
    if x_par == y_par:
        return
    
    if rnk[x_par] < rnk[y_par]:
        par[x_par] = y_par
    else:
        par[y_par] = x_par
        if rnk[x_par] == rnk[y_par]:
            rnk[x_par] += 1

for loop in range(q):
    c, x, y = map(int, raw_input().split())
    if c == 0:
        unite(x, y)
    else:
        print int(same(x, y))

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

n,q = [int(s) for s in input().split()]
par = []
for i in range(n):
    par.append(i)

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

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

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

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

Solution (Python):

import string
import sys
from itertools import chain, dropwhile, takewhile


def read(
    *shape, f=int, it=chain.from_iterable(sys.stdin), whitespaces=set(string.whitespace)
):
    def read_word():
        w = lambda c: c in whitespaces
        nw = lambda c: c not in whitespaces
        return f("".join(takewhile(nw, dropwhile(w, it))))

    if not shape:
        return read_word()
    elif len(shape) == 1:
        return [read_word() for _ in range(shape[0])]
    elif len(shape) == 2:
        return [[read_word() for _ in range(shape[1])] for _ in range(shape[0])]


def readi(*shape):
    return read(*shape)


def readi1(*shape):
    return [i - 1 for i in read(*shape)]


def readf(*shape):
    return read(*shape, f=float)


def reads(*shape):
    return read(*shape, f=str)


def arr(*shape, fill_value=0):
    if len(shape) == 1:
        return [fill_value] * shape[fill_value]
    elif len(shape) == 2:
        return [[fill_value] * shape[1] for _ in range(shape[0])]


def dbg(**kwargs):
    print(
        ", ".join("{} = {}".format(k, repr(v)) for k, v in kwargs.items()),
        file=sys.stderr,
    )


def main():
    sys.setrecursionlimit(100000)
    n, q = readi(2)
    par = arr(n + 1)
    for i in range(len(par)):
        par[i] = i

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

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        par[x] = y

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

    for _ in range(q):
        com, x, y = readi(3)
        if com == 0:
            unite(x, y)
        else:
            print(1 if same(x, y) else 0)


if __name__ == "__main__":
    main()

Solution (Python):
from typing import Union, List
import sys

sys.setrecursionlimit(100000)


def find(x: int, S: List[int]) -> int:
    if S[x] == x:
        return x
    else:
        S[x] = find(S[x], S)
        return S[x]


def same(x: int, y: int, S: List[int]) -> bool:
    return find(x, S) == find(y, S)


def unite(x: int, y: int, S: List[int]) -> None:
    rx = find(x, S)
    ry = find(y, S)
    if rx == ry:
        return None
    else:
        S[rx] = ry

if __name__ == '__main__':
    [n, q] = [int(i) for i in input().split()]

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

    for i in range(q):
        [com, x, y] = [int(i) for i in input().split()]
        if com == 0:
            unite(x, y, S)
        elif com == 1:
            if same(x, y, S):
                print('1')
            else:
                print('0')
        else:
            raise ValueError('value error')

Solution (Python):

import sys
sys.setrecursionlimit(10**7)
def init(n):
    return list(range(n+1))
def find(lis, x):
    if lis[x] == x:
        return x
    else:
        lis[x] = find(lis, lis[x])
        return lis[x]
def sameset(lis, x, y):
    return find(lis, x) == find(lis, y)
def union(lis, x, y):
    x = find(lis, x)
    y = find(lis, y)
    if x != y:
        lis[x] = y

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

Solution (Python):
class UF:
  def __init__(self,n):
    self.n = n
    self.p = [i for i in range(n)]
    self.r = [1]*n
    self.num = n
  
  def find(self,x):
    if x == self.p[x]:
      return x
    self.p[x] = UF.find(self,self.p[x])
    return self.p[x]
  
  def same(self,x,y):
    return UF.find(self,x) == UF.find(self,y)
  
  def unite(self,x,y):
    x = UF.find(self,x)
    y = UF.find(self,y)
    if x == y:
      return
    if self.r[x] < self.r[y]:
      x,y = y,x
    self.r[x] += self.r[y]
    self.p[y] = x
    self.num -= 1

  def size(self,x):
    return self.r[x]
  
  def count(self):
    return self.num

[n,q] = list(map(int,input().split()))
uf = UF(n)
for i in range(q):
  [com,x,y] = list(map(int,input().split()))
  x -= 1
  y -= 1
  if com == 0:
    uf.unite(x,y)
  else:
    if uf.same(x,y):
      print(1)
    else:
      print(0)

Solution (Python):
import sys

class UnionFind(object):
    def __init__(self):
        self.node_id = {}
        self.parent_id = []
        self.rank = []

    def find(self, node_id):
        while node_id != self.parent_id[node_id]:
            pp = self.parent_id[self.parent_id[node_id]]
            self.parent_id[node_id] = pp
            node_id = pp
        return node_id

    def add(self, x):
        if x in self.node_id:
            return self.node_id[x]
        node_id = len(self.node_id)
        self.node_id[x] = node_id
        self.parent_id.append(len(self.parent_id))
        self.rank.append(0)
        return node_id

    def union(self, p, q):
        i = self.find(p)
        j = self.find(q)
        if i == j:
            return
        if self.rank[i] < self.rank[j]:
            self.parent_id[i] = j
        elif self.rank[i] > self.rank[j]:
            self.parent_id[j] = i
        else:
            self.parent_id[j] = i
            self.rank[i] += 1

    def dump_groups(self):
        result = []
        group_id = {}
        for x, i in self.node_id.items():
            j = self.find(i)
            if j not in group_id:
                group_id[j] = len(result)
                result.append([])
            result[group_id[j]].append(x)
        return result

    def dump_dot(self):
        result = """digraph { graph [rankdir=LR];\n"""
        for i, target in enumerate(self.parent_id):
            result += """"%s" [label=\"%s\",shape=plaintext,shape=circle];\n""" % (i, i)
            if i != target:
                result += """"%s" -> "%s";\n""" % (i, target)
        result += "}"
        return result

uf = UnionFind()
(n, q) = sys.stdin.readline().split()
for i in range(int(n)):
    uf.add(i)
for i in range(int(q)):
    (c, x, y) = sys.stdin.readline().split()
    if c == "0":
        uf.union(int(x), int(y))
    else:
        print(1 if uf.find(int(x)) == uf.find(int(y)) else 0)

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

    def size(self, x):
        return self.siz[self.find(x)]
        
n, q = map(int, input().split())
union_find_tree = Union_Find(n)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        union_find_tree.union(x, y)
    else:
        if union_find_tree.same_checker(x, y):
            print(1)
        else:
            print(0)

Solution (Python):
import sys
input = sys.stdin.readline
def root(s):
    global pa
    if pa[s] == s:
        return s
    pa[s] = p = root(pa[s])
    return p

def unite(s, t):
    global pa
    a = root(s);b = root(t)
    if a == b:
        return 1
    elif rank[a] == rank[b]:
        pa[b] = a
        rank[a] += 1
    else:
        if rank[a] < rank[b]:
            pa[a] = b
        else:
            pa[b] = a

n, q = map(int, input().split())
pa = [i for i in range(n)]
rank = [1]*n
for i in range(q):
    a, b, c = map(int, input().split())
    if a == 0:unite(b,c)
    else:
        if root(b) == root(c):
            print(1)
        else:print(0)

Solution (Python):


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

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

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

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

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

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

Solution (Python):
def find(x):
    if(p[x] == x):return x
    else: 
        p[x] = find(p[x])
        return p[x]
def unite(x,y):
    x = find(x)
    y = find(y)

    if x==y:return
    if rank[x] < rank[y]:
        p[x] = y
    else:
        p[y] = x
        if rank[x] == rank[y]:
            rank[x]+=1

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

if __name__=='__main__':
    n, q = (int(x) for x in input().split())
    p = [i for i in range(n)]
    rank = [0 for i in range(n)]
        
    for i in range(q):
        com, x, y = (int(x) for x in input().split())
        if com == 0:unite(x,y)
        else:print(same(x,y))

Solution (Python):
import sys
import time
sys.setrecursionlimit(20000)

def find(tree,x):
    idx = tree[x]
    if(idx== x):
        return x
    else:
        root_idx = find(tree,tree[idx])
        return root_idx

def relate(tree,x,y,z):
    x_root_idx = find(tree,x)
    y_root_idx = find(tree,y)
    if(x_root_idx == y_root_idx):
        return False
    
    if (tree_rank[y_root_idx] < tree_rank[x_root_idx]):
        tree[y_root_idx] = (x_root_idx, z+tree[x][1]-tree[y][1])
    else:
        tree[x_root_idx] = (y_root_idx, -z-tree[x][1]+tree[y][1])
        if(tree_rank[x_root_idx]==tree_rank[y_root_idx]):
            tree_rank[y_root_idx] = tree_rank[y_root_idx] + 1
    

def diff(tree,x,y):
    x_idx = find(tree,x)
    y_idx = find(tree,y)
    if not(x_idx == y_idx):
        return "?"
    return tree[y][1] - tree[x][1]

def unite(tree,x,y):
    x_root_idx = find(tree,x)
    y_root_idx = find(tree,y)

    if not (x_root_idx == y_root_idx):
        if(tree_rank[x_root_idx] < tree_rank[y_root_idx]):
            tree[x_root_idx] = y_root_idx
        else:
            tree[y_root_idx] = x_root_idx
            if(tree_rank[x_root_idx] == tree_rank[y_root_idx]):
                tree_rank[x_root_idx] = tree_rank[x_root_idx] + 1

def same(tree,x,y):
    x_root_idx = find(tree,x)
    y_root_idx = find(tree,y)
    if(x_root_idx == y_root_idx):
        return True
    else:
        return False

if __name__ == '__main__':
    
    N,query_num = map(int, input().split())
    union_find_tree = [i for i in range(N)]
    tree_rank = [0]*N
    for i in range(query_num):
        operate,x,y = map(int, input().split())
        if(operate==0):
            unite(union_find_tree,x,y)
        if(operate==1):
            res = same(union_find_tree,x,y)
            if(res):
                print("1")
            else:
                print("0")

Solution (Python):


class UnionFind():

    def __init__(self, s):
        self.nodes = [-1 for _ in range(s)]

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

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

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


if __name__ == "__main__":
    n, q = map(int, input().split())
    sets = UnionFind(n)
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            sets.union(x, y)
        else:
            result = sets.is_same(x, y)
            if result is True:
                print("1")
            else:
                print("0")

Solution (Python):


_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'''


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

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

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

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


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


uf = UnionFind(N)

for _ in range(Q):
    P, A, B = map(int, input().split())

    
    if P == 0:
        uf.union(A, B)
    
    else:
        if uf.is_same(A, B):
            print(1)
        else:
            print(0)

Solution (Python):
import collections
import itertools
import operator


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

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)
        self.size = collections.defaultdict(lambda: 1)
        if x is not None:
            for elem in range(x+1):
                _, _, _ = self.parent[elem], self.rank[elem],self.size[elem]

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

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

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

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

    def grouper(self):
        roots = [(x, self.find(x_par)) for x, x_par in self.parent.items()]
        root = operator.itemgetter(1)
        for _, group in itertools.groupby(sorted(roots, key=root), root):
            yield [x for x, _ in group]

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

u = UnionFind(n)
for i in range(m):
	l = list(map(int,input().split()))
	if l[0]:
		print(int(u.are_same(l[1],l[2])))
	else:
		u.unite(l[1],l[2])

Solution (Python):
def fg(x):
    if g[x] == x:
        return x
    re = fg(g[x])
    g[x] = re
    return re


def kg(x, y):
    x = fg(x)
    y = fg(y)
    if d[y] > d[x]:
        g[x] = y
    else:
        g[y] = x
    if d[x] == d[y]:
        d[x] += 1


n, q = map(int, input().split())
d = [0] * n
g = [x for x in range(n)]
for _ in range(q):
    c, x, y = map(int, input().split())
    if c:
        print((fg(x) == fg(y))*1)
    else:
        kg(x, y)

Solution (Python):

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

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

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


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

uf = UnionFind(N)
for _ in range(Q):
    P, A, B = map(int, input().split())
    
    if P == 0:
        uf.union(A, B)
    
    else:
        if uf.is_same(A, B):
            print(1)
        else:
            print(0)

Solution (Python):
import sys

class UnionFind:
    def __init__(self, N:int):
        """N: 大きさ
        size: 連結成分の大きさ
        """
        self.par = [i for i in range(N)]
        self.size = [1]*N
        self.rank = [1]*N

    def root(self, x:int)->int:
        """根を求める"""
        if self.par[x] == x: 
            return x
        else:
            self.par[x] = self.root(self.par[x]) 
            return self.par[x]

    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)

    def unite(self, x:int, y:int):
        """y を x の属する集合に併合"""
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y: return
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        elif self.rank[root_x]<self.rank[root_y]:
            root_x,root_y = root_y,root_x
        
        self.par[root_y] = root_x
        self.size[root_x] += self.size[root_y]
        self.size[root_y] = 0 

    def get_size(self, x:int)->int:
        """xの属するグループのサイズ"""
        return self.size[self.root(x)]

if __name__ == "__main__":
    N,Q = map(int, sys.stdin.readline().split())
    UNITE,SAME = 0,1
    uf = UnionFind(N)
    for _ in range(Q):
        com,x,y = map(int, sys.stdin.readline().split())
        if com==UNITE:
            uf.unite(x, y)
        else: 
            print(int(uf.is_same(x, y)))

Solution (Python):
class UnionFindTree:
    '''
    Union Find Tree
    '''

    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

    def unite(self, x, y):
        self._unite(self.find(x), self.find(y))

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


n, q = map(int, input().split())
uft = UnionFindTree()
for i in range(n):
    uft.make(i)

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

Solution (Python):
import sys
sys.setrecursionlimit(2*10**6)
class UF():
 
    def __init__(self, num):
        self.par = [-1]*num
        self.size = [1]*num
    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 union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return 0
        if rx < ry:
            rx, ry = ry, rx
        self.par[rx] += self.par[ry]
        self.par[rx] = ry
        self.size[rx] += self.size[ry] 
        return 1
     
    def check(self, x, y):
        return self.find(x) == self.find(y)

n, q = map(int, input().split())
T = UF(n)
for _ in range(q):
    c, x, y = map(int, input().split())
    if c == 0:
        T.union(x, y)
    else:
        print(int(T.check(x, y)))

Solution (Python):


import collections
import itertools
import operator


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)


a,b =  map(int, input().split())
uf = UnionFind(a)
for i in range(b):
    com , x,y =map(int, input().split())
    if com == 0:
        uf.union(x, y)  
    elif com == 1:
        print(1 if uf.same_check(x, y) else 0)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self.p=[i for i in range(n)]
        self.r=[0 for i in range(n)]
    
    def root(self,x):
        if self.p[x]==x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.r[x]<self.r[y]:
            self.p[x]=y
        else:
            self.p[y]=x
            if self.r[x]==self.r[y]:
                self.r[x]+=1
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

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

Solution (Python):


import sys

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()



class UnionFind:
    
    
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  

    def root(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.root(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.root(x), self.root(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  
                
                
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                
                
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x


n, q = LI()
query = [LI() for _ in range(q)]

uf = UnionFind(n)
for com, x, y in query:
    if com == 0:  
        uf.unite(x, y)
    else:  
        if uf.root(x) == uf.root(y):
            print(1)
        else:
            print(0)

Solution (Python):



import collections


class UnitDict(dict):

    def __init__(self, iterable=None, wrapper=lambda x: x):
        super().__init__(self)
        self.wrapper = wrapper
        if iterable is not None:
            self.update(iterable)

    def __missing__(self, key):
        self[key] = self.wrapper(key)
        return self[key]


class DisjointSetDataStructure(object):

    def __init__(self, nodes=None):
        self.par = UnitDict(wrapper=lambda x: x)
        self.rank = collections.defaultdict(int)
        self.groups = UnitDict(wrapper=lambda x: {x})
        if nodes is not None:
            for node in nodes:
                _, _, _ = self.par[node], self.rank[node], self.groups[node]
        
    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r
    
    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)
    
    def elements_of_group(self, node):
        return self.groups[self.root(node)]
 
    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            self.par[y] = x
            self.groups[x].update(self.groups[y])
            self.groups[y].clear()
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


def main():
    _, q = [int(z) for z in input().split()]
    d = DisjointSetDataStructure()
    for _ in range(q):
        
        c, x, y = input().split()
        if c == "0":
            d.unite(x, y)
        else:
            print(int(d.in_the_same_set(x, y)))


if __name__ == "__main__":
    main()

Solution (Python):
def get_root(nodes, x: int) -> int:
    if nodes[x] < 0:
        return x
    else:
        nodes[x] = get_root(nodes, nodes[x])
        return nodes[x]


def unite(nodes, x: int, y: int) -> None:
    root_x, root_y = get_root(nodes, x), get_root(nodes, y)
    if root_x != root_y:
        bigroot, smallroot = \
            (root_x, root_y) if nodes[root_x] < nodes[root_y] else (root_y, root_x)
        nodes[bigroot] += nodes[smallroot]
        nodes[smallroot] = bigroot


if __name__ == "__main__":
    import sys
    N, Q = map(int, input().split())
    nodes = [-1]*N
    result = []
    append = result.append

    for p, a, b in (map(int, l.split()) for l in sys.stdin):
        if not p:
            unite(nodes, a, b)
        else:
            append(1 if get_root(nodes, a) == get_root(nodes, b) else 0)

    print(*result, sep="\n")

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
parent = [i for i in range(n)]
def get_par(x):
  if x == parent[x]:return x
  parent[x] = get_par(parent[x])
  return parent[x]

for _ in range(q):
  com, x, y = map(int, input().split())
  px, py = get_par(x), get_par(y)
  if com == 0:
    parent[px] = py
  else:
    print(int(px == py))

Solution (Python):
def root(x):
    if parent[x] == x:
        return(x)
    else:
        parent[x] = root(parent[x])
        return(parent[x])


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


def union(x, y):
    x = root(x)
    y = root(y)
    if(x == y):
        return

    parent[x] = min(x, y)
    parent[y] = min(x, y)
    return


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

parent = {i: i for i in range(n)}
for _ in range(q):
    com, x, y = map(int, input().split())

    if com == 1:
        print(int(same(x, y)))

    else:
        union(x, y)