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, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N, Q = map(int, input().split())
QE = [list(map(int, input().split())) for _ in range(Q)]

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 same_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:
            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
            self.size[x] += self.size[y]

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


uni = UnionFind(N)
for qe in QE:
    com, x, y = qe
    if com==0:
        uni.union(x, y)
    elif com==1:
        if uni.same_check(x, y):
            print(1)
        else:
            print(0)
    else:
        print('miss')

Solution (Python):


class UF:
    def __init__(self,n):
        self.n = n
        self.root = [-1]*n 
        self.rank = [0]*n 
    def __del__(self):
        pass
        
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
            
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[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) 
    
    def count(self,x):
        return -self.root[self.find(x)]
    
N,Q = map(int,input().split())
uf = UF(N)

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

Solution (Python):
import sys

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, sys.stdin.readline().strip().split())

uf = UnionFind(n)
for _ in range(q):
    query_type, x, y = map(int, sys.stdin.readline().strip().split())
    if query_type == 0:
        uf.union(x, y)
    elif query_type == 1:
        is_same = uf.same(x, y)
        print(1 if is_same else 0)

Solution (Python):
rank = []
p = []


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


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


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


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


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


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

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

Solution (Python):


class UnionFind:
    """
    par  : 木の親要素を管理par[x]==xのときそのノードは根,
            初期状態例:[0,1,2,3]それぞれが親
                        [0,0]のとき0が根で1の親は0であることを示す
    rank : 木の高さを格納,併合する際に木の高さが高いものに低いものをくっつける形になるから

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

    """
    引数のノードの根を検索
    再起関数で親の親の親の...という形で根にたどり着くまで繰り返す
    """
    
    def findSet(self, x):
        
        if self.par[x] == x:
            return x
        else:
        
            
            self.par[x] = self.findSet(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        
        x = self.findSet(x)
        y = self.findSet(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.findSet(x) == self.findSet(y)


def main():
    p = []  
    n, q = map(int, input().split())
    
    
    
    i = 0
    while i < q:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;
    x = UnionFind(n)

    i = 0
    while i < len(p):
        if(p[i][0] == 0):
                x.union(p[i][1],p[i][2])
        if(p[i][0] == 1):
            result = x.same_check(p[i][1],p[i][2])
            if result == False:
                print(0)
            if result == True:
                print(1)

        i = i + 1







if __name__ == '__main__':
    main()

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

class UnionFind:
    N = 0
    cost = 0
    par = []
    
    def init(N):
        UnionFind.N = N
        UnionFind.par = [i for i in range(N)]

    def find(v):
        c = 0
        u = v
        while v != UnionFind.par[v]:
            v = UnionFind.par[v]
            c += 1

        if c > 10:
            while u != v: u, UnionFind.par[u] = UnionFind.par[u], v

        return v

    def union(v, u, c=0):
        vr = UnionFind.find(v)
        ur = UnionFind.find(u)

        if vr == ur: return True

        UnionFind.par[ur] = vr
        UnionFind.cost += c

        return False
            
    def get_cost():
        return UnionFind.cost

    def same(v, u):
        return UnionFind.find(v) == UnionFind.find(u)

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

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

        if com == 0: UnionFind.union(x, y)
        else: 
            if UnionFind.same(x, y): print(1)
            else: print(0)

if __name__ == '__main__':
    main()

Solution (Python):
def makeSet(x):
    p[x] = x
    rank[x] = 0

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

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

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

n,q = map(int, input().split())
p = [0]*n
rank = [0]*n

for x in range(n):
    makeSet(x)

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

Solution (Python):

def makeSet(x):
    global p, rank
    p[x] = x
    rank[x] = 0

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

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

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

def isSame(x, y):
    global p
    if(findSet(x) == findSet(y)):
        return True
    else:
        return False

if __name__ == "__main__":
    N, Q = (int(z) for z in input().split())
    p = [None] * N
    rank = [None] * N

    for i in range(N):
        makeSet(i)

    for i in range(Q):
        com_i, x, y = (int(z) for z in input().split())
        if(com_i == 0):
            
            union(x, y)
        if(com_i == 1):
            
            if(isSame(x, y) == False):
                print("0")
            else:
                print("1")

Solution (Python):
class Disjointset:

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

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

    def unite(self,x,y): return self.link(self.findSet(x), self.findSet(y))

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

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

n,q = map(int,input().split())
ds = Disjointset(n)
ans = []
for _ in range(q): 
    com,x,y = map(int,input().split())
    if com == 0: ds.unite(x,y)
    else: ans.append("1" if ds.same(x,y) else "0")
print("\n".join(ans))

Solution (Python):
maxn = 100000

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

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


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


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

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

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

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

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

    def print_set(self):
        print(self.parent)
        print(self.rank)

    def find_set(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find_set(self.parent[x])
        
        return self.parent[x]
    
    def unite(self, x, y):
        x_parent = self.find_set(x)
        y_parent = self.find_set(y)

        if self.rank[x_parent] > self.rank[y_parent]:
            self.parent[y_parent] = x_parent
        else:
            self.parent[x_parent] = y_parent
            if self.rank[x_parent] == self.rank[y_parent]:
                self.rank[y_parent] += 1

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

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

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

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

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

    def connect(self, a, b) -> bool:
        a = self.root(a)
        b = self.root(b)

        if a == b:
            return False

        if self.size(a) < self.size(b):
            a, b = b, a

        self.parent[a] += self.parent[b]

        self.parent[b] = a

        return True


n, q = map(int, input().split())
unif = UnionFind(n)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        unif.connect(x, y)
    else:
        print(1 if unif.root(x) == unif.root(y) else 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)
for i 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):
n, q = map(int, input().split())
p = [-1]*n

def root(x):
    if p[x]==-1:
        return x
    
    p[x] = root(p[x])
    return p[x]

def unite(a, b):
    if root(a)!=root(b):
        if a>b:
            a,b = b,a
        p[root(b)] = root(a)
        
def same(a, b):
    if root(a)==root(b):
        return True
    else:
        return False
    
for i in range(q):
    c, a, b = map(int, input().split())
    if c==0:
        unite(a, b)
       
    if c==1:
        if same(a, b):
            print(1)
        else:
            print(0)

Solution (Python):



n,q=map(int,input().split())
parents=[i for i in range(n)]
deepth=[0 for _ in range(n)]

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

def unite(x,y):
    px=find(x)
    py=find(y)
    if deepth[px]>deepth[py]:
        parents[py]=px
        deepth[px]=max(deepth[px],deepth[py]+1)
    else:
        parents[px]=py
        deepth[py]=max(deepth[py],deepth[px]+1)

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

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

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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

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



def main():
    n, _, *A = map(int, open(0).read().split())
    uf = UnionFind(n)

    for a, x, y in zip(*[iter(A)]*3):
        if a == 0:
            uf.unite(x, y)
        else:
            print(1 if uf.same(x, y) else 0)

if __name__ == '__main__':
    main()

Solution (Python):
n, q = map(int, 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 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())

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

Solution (Python):

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

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

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

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

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


if __name__ == '__main__':
    main()

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

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

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

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

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


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

    ds = DisjointSet(n)

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

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

par = [-1]*(n+1)

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

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


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

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

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

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

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


if __name__ == "__main__":
    N, Q = map(int, input().split())
    uf = UF_tree(N)
    ans = []
    for _ in range(Q):
        com, x, y = map(int, input().split())
        if com:
            ans.append(uf.isSame(x, y))
        else:
            uf.unite(x, y)
    print(*ans, sep="\n")

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

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

parents = [-1] * n

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

def union(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return

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

    parents[x] += parents[y]
    parents[y] = x     

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

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

    if com == 0:
        union(x, y)
    else:
        if same(x, y):
            print(1)
        else:
            print(0)

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

    
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

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

    
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


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

Solution (Python):








import sys
sys.setrecursionlimit(10 ** 5 + 10)


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

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

        def get_size(self, x):
            """
            x が属するグループの要素数
            """
            x = self.find(x)
            return self.size[x]

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

    for i 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)


resolve()

Solution (Python):
from collections import deque

def get_input():
  return list(map(int, input().split(' ')))

(n, q) = get_input()

d = [] 

for _ in range(q):
  c = get_input()
  if c[0] == 0: 
    i1 = None
    i2 = None
    for i in range(len(d)):
      s = d[i]
      if c[1] in s or c[2] in s:
        if i1 != None:
          i2 = i
          d[i1] = d[i1] | s
          d.pop(i2)
          break
        else:
          i1 = i
    if i1 == None:
      d.append({c[1],c[2]})
    elif i2 == None:
      d[i1] = d[i1] | {c[1],c[2]}
  elif c[0] == 1: 
    p = False
    for s in d:
      if c[1] in s or c[2] in s:
        if c[1] in s and c[2] in s:
          print(1)
        else:
          print(0)
        p = True
        break
    if not p:
      print(0)

Solution (Python):
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

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


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

n, q = map(int, input().split())
par = [-1 for i in range(n)]

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

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

    def makeSet(self, x):
        self.parent.append(x)
        self.rank.append(0)

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

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

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

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


import sys


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

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

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

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

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

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


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

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