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
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())

class Uf:
    def __init__(self, N):
        self.Par = list(range(N + 1))

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

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.Par[x] = y

uf = Uf(N)
for i in range(Q):
    com, x, y = map(int, input().split())
    if com==0:
        uf.unite(x, y)
    else:
        print(int(uf.same(x, y)))

Solution (Python):
def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    P[root(x)] = root(y)
N,Q = map(int,input().strip().split(" "))
P = [i for i in range(N)]
for i in range(Q):
    com,x,y = map(int,input().strip().split(" "))
    if com == 0:
        unite(x,y)
    else:
        if is_same_set(x,y):
            print(1)
        else:
            print(0)

Solution (Python):
n,q=map(int,input().strip().split(' '))
P = [i for i in range(n)]
def root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    P[root(x)] = root(y)

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

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


def find_group(groups: Dict[int, List], tgt: str) -> (bool, str):
    for k, v in groups.items():
        if tgt in v:
            return k
    return "-1"


def main():
    n, q = map(int, input().split())
    query_lines = sys.stdin.readlines()
    queries = [query_lines[x].split() for x in range(q)]

    answers = [None] * q
    num_ans = 0

    groups = {str(i): [str(i)] for i in range(n)}
    groups_memo = {str(i): str(i) for i in range(n)}

    for query in queries:
        if query[0] == '0':     
            q1 = query[1]
            q2 = query[2]
            g1 = find_group(groups, q1)
            g2 = find_group(groups, q2)
            if g1 == g2:
                continue
            assert g1 != -1 and g2 != -1
            for item in groups[g2]:
                groups_memo[item] = g1
            groups[g1] = groups[g1] + groups[g2]
            del groups[g2]
        else:                   
            if groups_memo[query[1]] == groups_memo[query[2]]:
                answers[num_ans] = 1
            else:
                answers[num_ans] = 0
            num_ans += 1

    [print(answers[x]) for x in range(num_ans)]
    return


main()

Solution (Python):
from sys import stdin

class DisjointSet(object):
    def __init__(self, n):
        self.parent = [None] * (n+1)
        self.rank = [None] * (n+1)

    def make_set(self, x):
        if self.parent[x] == None:
            self.parent[x] = x
            self.rank[x] = 0

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

def read_and_print_ds(n, q):
    ds = DisjointSet(n)
    for _ in range(q):
        line = [ int(i) for i in stdin.readline().strip().split() ]
        s1 = line[1]
        s2 = line[2]
        if line[0] == 0:
            ds.make_set(s1)
            ds.make_set(s2)
            ds.unite(s1, s2)
        else:
            ds.make_set(s1)
            ds.make_set(s2)
            if ds.same(s1, s2):
                print("1")
            else:
                print("0")

n, q = [ int(i) for i in input().split() ]
read_and_print_ds(n, q)

Solution (Python):
class UnionFind:
    def __init__(self, n):
        self._tree = [i for i in range(n)]
        self._rank = [1] * n
    def root(self, a):
        if self._tree[a] == a:return a
        self._tree[a] = self.root(self._tree[a])
        return self._tree[a]
    def is_same_set(self, a, b):
        return self.root(a)==self.root(b)
    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._rank[ra] < self._rank[rb]:
            self._tree[ra] = rb
        else:
            self._tree[rb] = ra
            if self._rank[ra] == self._rank[rb]:
                self._rank[ra] += 1

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

Solution (Python):
class UnionFindTree:    
    def __init__(self,n):
        self.a = [i for i in range(n)]
        self.rank = [1 for i in range(n)]

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

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

    def union(self,x,y):
        rx = self.root(x)
        ry = self.root(y)
        if rx != ry:
            if self.rank[rx] < self.rank[ry]:
                self.a[rx] = ry
            else:
                self.a[ry] = rx
                if self.rank[rx] == self.rank[ry]:
                    self.rank[rx] += 1
            
                

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

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

Solution (Python):

"""
Created on Sat Oct  6 08:39:16 2018
DSL_1_A
@author: maezawa
"""

class djset:
    def __init__(self, size):
        self.rank = [0]*size
        self.parent = [0]*size
        for i in range(size):
            self.makeset(i)
            
    def makeset(self, x):
        self.parent[x] = x
        self.rank[x] = 0
        
    def same(self, x, y):
        return self.findset(x) == self.findset(y)
    
    def unite(self, x, y):
        self.link(self.findset(x), self.findset(y))
        
    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
                
    def findset(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]
               

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

for i in range(q):
    com, xq, yq = list(map(int, input().split()))
    if com == 0:
        ds.unite(xq, yq)
    elif com == 1:
        if ds.same(xq, yq):
            print(1)
        else:
            print(0)

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


class UnionFind:
    def __init__(self,arg_V):
        self.V = arg_V
        self.boss = [None]*arg_V
        self.height = [None]*arg_V

    def init(self):
        for i in range(self.V):
            self.boss[i] = i
            self.height[i] = 0

    def get_boss(self,index):
        if index == self.boss[index]:
            return index
        else:
            self.boss[index] = self.get_boss(self.boss[index])
            return self.boss[index]


    def is_same_group(self,a,b):
        return self.get_boss(a) == self.get_boss(b)

    def unite(self,x,y):
        boss_x = self.get_boss(x)
        boss_y = self.get_boss(y)

        if boss_x == boss_y:
            return

        if self.height[x] > self.height[y]:

            self.boss[boss_y] = boss_x

        elif self.height[x] < self.height[y]:

            self.boss[boss_x] = boss_y

        else:
            self.boss[boss_y] = boss_x
            self.height[x] += 1

class Edge:
    def __init__(self,arg_FROM,arg_TO,arg_WEIGHT):
        self.FROM = arg_FROM
        self.TO = arg_TO
        self.WEIGHT = arg_WEIGHT

    def __lt__(self,arg):
        return self.WEIGHT < arg.WEIGHT



V,num_query = map(int,input().split())

UF = UnionFind(V)
UF.init()

for loop in range(num_query):

    command,A,B = map(int,input().split())
    if command == 0:
        UF.unite(A, B)
    else:
        if UF.is_same_group(A, B) == True:
            print("1")
        else:
            print("0")

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

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

    def same(self, x, y):
        return 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 unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))


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

    for i in range(q):
        com, x, y = [int(v) for v in input().split()]
        if com == 0:
            ds.unite(x, y)
        elif com == 1:
            if ds.same(x, y):
                print(1)
            else:
                print(0)

Solution (Python):
import queue


class UnionFind:

    def __init__(self, N):
        self.sizes = [1 for _ in range(N)]
        self.par = [i for i in range(N)]

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

        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.sizes[x] < self.sizes[y]:
            x, y = y, x

        self.par[y] = x
        self.sizes[x] += self.sizes[y]

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

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


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

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

    return


if __name__ == '__main__':
    main()

Solution (Python):
class UFT(object):
    def __init__(self):
        self.par={i:i for i in range(10001)}
        self.rank={i:0 for i in range(10001)}
    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 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 unite_chk(self,a,b):
        return self.find(a)==self.find(b)
        
obj=UFT()
n,q=map(int,input().split())
for _ in range(q):
    c,x,y=map(int,input().split())
    if c:
        print(int(obj.unite_chk(x,y)))
    else:
        obj.unite(x,y)