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

class UF:
    """Union Find
    """
    def __init__(self, n):
        self.n = n
        self.elements = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def union(self, v, w):
        assert 0 <= v < self.n
        assert 0 <= w < self.n
        rv = self.root(v)
        rw = self.root(w)

        if rv != rw:
            if self.size[rv] > self.size[rw]:
                self.elements[rw] = rv
                self.size[rv] += self.size[rw]
            else:
                self.elements[rv] = rw
                self.size[rw] += self.size[rv]

    def connected(self, v, w):
        assert 0 <= v < self.n
        assert 0 <= w < self.n
        return self.root(v) == self.root(w)

    def root(self, v):
        rv = self.elements[v]
        while rv != self.elements[rv]:
            rv = self.elements[rv]
        return rv


def run():
    n, q = [int(x) for x in input().split()]
    uf = UF(n)

    for _ in range(q):
        com, i, j = [int(x) for x in input().split()]
        if com == 0:
            uf.union(i, j)
        elif com == 1:
            if uf.connected(i, j):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    run()

Solution (Python):
N, Q = map(int, input().split())
union = [x for x in range(N)]
answer_list = []

def fetch_root(idx) :
    if idx == union[idx] :
        return idx
    else :
        union[idx] = fetch_root(union[union[idx]])
        return union[idx]

for i in range(Q) :
    q, a, b = map(int, input().split())
    
    
    if q == 0 :
        min_root_idx = max(fetch_root(a), fetch_root(b))
        union[min_root_idx] = min(fetch_root(a), fetch_root(b))
        
    
    else :
        if fetch_root(union[a]) == fetch_root(union[b]) :
            answer_list.append(1)
        else :
            answer_list.append(0)
            
for i in answer_list :
    print(i)

Solution (Python):
n, q = map(int, input().split())
union = [x for x in range(n)]
answer = []

def root(idx) :
    if idx == union[idx] :
        return idx
    else :
        union[idx] = root(union[idx])
        return union[idx]

for i in range(q) :
    com, x, y = map(int, input().split())
    
    
    if com == 0 :
        min_root = min(root(x), root(y))
        union[root(x)] = union[root(y)] = min_root
        
    
    else :
        if root(x) == root(y) :
            answer.append("1")
        else :
            answer.append("0")
            
for i in answer :
    print(i)

Solution (Python):
n, p = map(int, input().split())
nodes = [x for x in range(n)]
answer = []

def get_root(idx) :
    if idx == nodes[idx] :
        return idx
    else :
        nodes[idx] = get_root(nodes[idx])
        return nodes[idx]
        
for i in range(p) :
    q, a, b = map(int, input().split())
    
    
    if q == 0 :
        parent_min = min(get_root(a), get_root(b))
        nodes[get_root(a)] = nodes[get_root(b)] = parent_min
        
    
    else :
        if get_root(a) == get_root(b) : answer.append(1)
        else : answer.append(0)
            
for i in answer :
    print(i)

Solution (Python):
n, p = map(int, input().split())
nodes = [x for x in range(n)]
answer = []

def get_root(idx) :
    if idx == nodes[idx] :
        return idx
    else :
        
        return get_root(nodes[idx])
        
for i in range(p) :
    q, a, b = map(int, input().split())
    
    
    if q == 0 :
        parent_min = min(get_root(a), get_root(b))
        nodes[get_root(a)] = nodes[get_root(b)] = parent_min
        
    
    else :
        if get_root(a) == get_root(b) : answer.append(1)
        else : answer.append(0)
            
for i in answer :
    print(i)

Solution (Python):



class DisjointSets:
    '''
    Implementing disjoint sets using disjoint sets forests structure.
    '''

    def __init__(self, size):
        self.ranks = [0] * size
        self.roots = [0] * size
        for x in range(size):
            self.make_set(x)

    def make_set(self, x):
        self.roots[x] = x
        self.ranks[x] = 0

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

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

        return self.roots[x]

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

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


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

    for line in sys.stdin.readlines():
        query, x, y = map(int, line.strip().split())
        if query == 0:
            ds.unite(x, y)
        elif query == 1:
            if ds.in_same_set(x, y):
                print(1)
            else:
                print(0)

Solution (Python):

class DisjointSets:
    '''
    Implementing disjoint sets using disjoint sets forests structure.

    --- methods ---
    __init__(size): size should be the number of elements in this disjoint sets
    unite(x, y): unite sets that contain x and y into a new set
    same(x, y): check if x and y are in the same set
    '''

    def __init__(self, size):
        self.size = size
        self.ranks = [0] * self.size
        self.roots = [0] * self.size
        for x in range(self.size):
            self._make_set(x)

    def _make_set(self, x):
        self.roots[x] = x
        self.ranks[x] = 0

    def _link(self, x, y):
        if self.ranks[x] > self.ranks[y]:
            self.roots[y] = x
        else:
            self.roots[x] = y
            if self.ranks[x] == self.ranks[y]:
                self.ranks[y] += 1

    def _find_set(self, x):
        
        if x != self.roots[x]:
            self.roots[x] = self._find_set(self.roots[x])

        return self.roots[x]

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))

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


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

    for line in sys.stdin.readlines():
        query, x, y = map(int, line.strip().split())
        if query == 0:
            ds.unite(x, y)
        elif query == 1:
            if ds.same(x, y):
                print(1)
            else:
                print(0)

Solution (Python):

class DisjointSets:
    '''
    Implementing disjoint sets using disjoint sets forests structure.

    --- methods ---
    __init__(size): size should be the number of elements in this disjoint sets
    unite(x, y): unite sets that contain x and y into a new set
    same(x, y): check if x and y are in the same set
    '''

    def __init__(self, size):
        self.size = size
        self.roots = [x for x in range(self.size)]
        self.ranks = [0] * self.size

    def _link(self, x, y):
        if self.ranks[x] > self.ranks[y]:
            self.roots[y] = x
        else:
            self.roots[x] = y
            if self.ranks[x] == self.ranks[y]:
                self.ranks[y] += 1

    def _find_set(self, x):
        
        if x != self.roots[x]:
            self.roots[x] = self._find_set(self.roots[x])

        return self.roots[x]

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))

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


if __name__ == '__main__':
    '''
    an example of using this function
    AIZU ONLINE JUDGE - DSL_1_A
    '''

    import sys
    n, q = map(int, input().split())
    ds = DisjointSets(n)

    for line in sys.stdin.readlines():
        query, x, y = map(int, line.strip().split())
        if query == 0:
            ds.unite(x, y)
        elif query == 1:
            if ds.same(x, y):
                print(1)
            else:
                print(0)

Solution (Python):

import time

N,Q = map(int,input().split())
rank = [0 for i in range(N)]

class Tree:
    def __init__(self,par,key):
        self.par = par
        self.key = key

List = [Tree(i,i) for i in range(N)]

def unit(x,y):
    while List[x].par != x:
        x = List[x].par
    a = rank[x]
            
    while List[y].par != y:
        y = List[y].par
    b = rank[y]
    if a <= b:
        if a == b:
            rank[x] += 1
        List[y].par = x
    else:
        List[x].par = y



def Find(x,y):
    Q = []
    P = []
    while List[x].par != x:
        x = List[x].par
        Q.append(x)
            
    while List[y].par != y:
        y = List[y].par
        P.append(y)
    for xi in Q:
        List[xi].par = x
        rank[xi] = 1
    for yi in P:
        List[yi].par = y
        rank[yi] = 1
    if x == y:
        print(1)
    else:
        print(0)
    
        
for i in range(Q):
    com, x,y = map(int,input().split())

    if com == 0:
        unit(x,y)
            
    else:
        Find(x,y)

Solution (Python):
class UnionFind:
    V = -1
    par, rnk, sz = [], [], []
    def __init__(self, V):
        import sys
        sys.setrecursionlimit(1000000000)
        self.V = V;
        self.par = [i for i in range(V)]
        self.rnk = [0] * V
        self.sz = [1] * V
        
    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.rnk[x] < self.rnk[y]:
            self.par[x], self.sz[y] = y, self.sz[y] + self.sz[x] 
        else:
            self.par[y], self.sz[x] = x, self.sz[x] + self.sz[y]
            if self.rnk[x] == self.rnk[y]:
                self.rnk[x] = self.rnk[x] + 1
                
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def size(self, x):
        return self.sz[self.find(x)]

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

Solution (Python):
from sys import stdin


class DisjointSet():
    def __init__(self):
        self.parent = None
        self.ancestor = self


def ancestor(elems, x):
    s = elems[x].ancestor
    while s.parent is not None:
        s = s.parent
    elems[x].ancestor = s
    return s


def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        parent = DisjointSet()
        ax.parent = ay.parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

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


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin


class DisjointSet():
    def __init__(self):
        self.parent = None
        self.ancestor = self


def ancestor(elems, x):
    s = elems[x].ancestor
    while s.parent is not None:
        s = s.parent
    elems[x].ancestor = s
    return s


def unite(elems, x, y):
    ax = ancestor(elems, x)
    ay = ancestor(elems, y)
    if ax is not ay:
        ax.parent = ay
        ax.ancestor = ay.ancestor


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

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


if __name__ == '__main__':
    main()

Solution (Python):
class DisjointSetElement():
    def __init__(self):
        self.parent = None
        self.anc = self

    def ancestor(self):
        s = self.anc
        while s.parent is not None:
            s = s.parent
        self.anc = s
        return s

    def unite(self, y):
        ax = self.ancestor()
        ay = y.ancestor()
        if ax is not ay:
            ax.parent = ay
            ax.anc = ay.anc

    def same(self, y):
        return self.ancestor() is y.ancestor()


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSetElement() for _ in range(n)]

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


if __name__ == '__main__':
    main()

Solution (Python):
class DisjointSetElement():
    def __init__(self, x):
        self.parent = x
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.elems = [DisjointSetElement(n) for n in range(n)]

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

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

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

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))


def main():
    n, q = [int(x) for x in input().split()]
    ds = DisjointSet(n)

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


if __name__ == '__main__':
    main()

Solution (Python):

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

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

  def union(self, x, y):
    x = self.find_set(x)
    y = self.find_set(y)
    if x == y:
      return
    if self.rank[x] > self.rank[y]: 
      self.par[y] = x
    else:
      self.par[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)

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.union(X, Y)

  elif C == 1:
    print(1 if uf.same(X, Y) else 0)
  else:
    print(uf.find_set(X))

Solution (Python):





import sys
input = sys.stdin.readline


from collections import deque

def main():
    (n,q) = map(int,input().split())
    s = [i for i in range(n)]
    dq = [deque() for i in range(n)]
    for i in range(n):
        dq[i].append(i)
    
    
    for i in range(q):
        (a,b,c) = map(int,input().split())
        
        if a == 0:
            sb = s[b]
            sc = s[c]
            if sb == sc:
                continue
            dq[sb].extend(dq[sc])
            dq[sc] = None
            for j in dq[sb]:
                s[j] = sb
        elif a == 1:
            if c in dq[s[b]]:
                print ("1")
            else:
                print("0")
    
if __name__ == '__main__':
    main()

Solution (Python):
class Node():
    def __init__(self, id):
        self.id = id
        self.p = self
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.nodes = {}
        for i in range(n):
            self.makeSet(i)

    def makeSet(self, i):
        self.nodes[i] = Node(i)

    def findSet(self, x):
        if x.p is not x:
            x.p = self.findSet(x.p)
        return x.p

    def unite(self, x, y):
        
        px = self.findSet(x)
        py = self.findSet(y)
        if px.rank > py.rank:
            py.p = px
        else:
            px.p = py
        if x.rank == y.rank:
            py.rank += 1

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


n, q = map(int, input().split())
uf = DisjointSet(n)
for i in range(q):
    com, ix, iy = map(int, input().split())
    if com == 0:
        
        uf.unite(uf.nodes[ix], uf.nodes[iy])
    else:
        
        print(1 if uf.bool(uf.nodes[ix], uf.nodes[iy]) else 0)

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

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] = rank[y] + 1
def findset(x):
    if x != p[x]:
        p[x] = findset(p[x])
    return p[x]

t,s = map(int,input().split())
for i in range(t):
    p.append(None)
    rank.append(None)
while True:
    try:
        o,x,y = map(int,input().split())
    except:
        break
    else:
        if o == 0:
            if p[x] == None:
                makeset(x)
            if p[y] == None:
                makeset(y)
            union(x,y)
        else:
            if p[x] == None:
                makeset(x)
            if p[y] == None:
                makeset(y)
            if findset(x) == findset(y):
                answer.append(1)
            else:
                answer.append(0)
for i in range(len(answer)):
    print(answer[i])

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

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

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

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


def unite(x, y):
 union(x, y)

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

 if x == y:
  return 1
 else :
  return 0


output = []

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

 if com == 0:
  unite(x, y)
 else :
  output.append(same(x,y))

for ans in output:
 print(ans)

Solution (Python):


import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')


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

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

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

    
    def is_tree(self, x):
        return self.tree[self.find(x)]

    
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        
        return len(res) - 1

N,Q=MAP()
uf=UnionFind(N)
for _ in range(Q):
    com,x,y=MAP()
    if com==0:
        uf.union(x, y)
    else:
        print(int(uf.same(x, y)))

Solution (Python):
COM_UNITE = 0
COM_SAME = 1


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

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[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)


if __name__ == '__main__':
    n, q = (int(s) for s in input().split())
    tree = UnionFindTree(n)

    for i in range(q):
        com, x, y = (int(s) for s in input().split())
        if com == COM_UNITE:
            tree.unite(x, y)
        elif com == COM_SAME:
            print(int(tree.same(x, y)))

Solution (Python):
COM_UNITE = 0
COM_SAME = 1


class UnionFind():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[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)


if __name__ == '__main__':
    n, q = (int(s) for s in input().split())
    tree = UnionFind(n)

    for i in range(q):
        com, x, y = (int(s) for s in input().split())
        if com == COM_UNITE:
            tree.unite(x, y)
        else:
            print(int(tree.same(x, y)))

Solution (Python):
class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in xrange(size)]

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

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

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


def main():
    n, q = map(int, raw_input().split())
    uf = UnionFind(n)
    for _ in xrange(q):
        com, x, y = map(int, raw_input().split())
        if com == 0:
            uf.union(x, y)
        else:
            print 1 if uf.same(x, y) else 0

if __name__ == "__main__":
    main()

Solution (Python):
import sys
f = sys.stdin

def unite(x, y):
    global dat
    x, y = find(dat, x), find(dat, y)
    if x == y:
        return True
    if dat[y] < dat[x]:
        x, y = y, x
    dat[x] += dat[y]
    dat[y] = x
    return False
        

def same(x, y):
    global dat
    x, y = find(dat, x), find(dat, y)
    print(1 if x == y else 0)
def find(dat, x):
    if dat[x] < 0:
        return x
    dat[x] = find(dat, dat[x])
    return dat[x]

com = (unite, same)

n, q = map(int, f.readline().split())
dat = [-1] * n

for c, x, y in (map(int, f.readline().split()) for _ in range(q)):
    com[c](x, y)

Solution (Python):
class union_find:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:return True
        
        if self.table[y] < self.table[x]:x, y = y, x

        self.table[x] += self.table[y]
        self.table[y] = x
        return False
            
    def find(self, x):
        if self.table[x] < 0:return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]

import sys
f = sys.stdin

n, q = map(int, f.readline().split())
uf = union_find(n)

op = (uf.union, lambda x, y:print(1 if uf.find(x) == uf.find(y) else 0))

for com, x, y in (map(int, f.readline().split()) for _ in range(q)):
    op[com](x, y)

Solution (Python):


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

def union(x, y, p, rank):
    link( findSet(x, p, rank), findSet(y, p, rank), p, rank)
    
def findSet(x, p, rank):
    if  x != p[x] :
        p[x] = findSet(p[x], p, rank)
    return p[x]
    
def isSameSet(x, y, p, rank): 
    if findSet(x, p, rank) == findSet(y, p, rank): print 1
    else: print 0   
    
def link(x, y, p, rank):
    if  rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if  rank[x] == rank[y]  :
            rank[y] += 1

n,q = map(int,raw_input().split())
p = [i for i in range(n)] 
rank = [0 for i in range(n)]
for i in range(q):
    com, x, y = map(int,raw_input().split())
    if com: 
        isSameSet(x, y, p, rank)
    else: 
        union(x, y ,p , rank)

Solution (Python):
class UnionFind:
    def __init__(self, size):
        self.rank = [0] * size
        self.par = range(size)
        self.g_num = size

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

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

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

        self.g_num -= 1
        if (self.rank[x] > self.rank[y]):
            self.par[y] = x
        else:
            self.par[x] = y
            if (self.rank[x] == self.rank[y]): self.rank[y] += 1

    def group_num(self):
        return self.g_num

n, q = map(int, raw_input().split())
uf = UnionFind(n)
for i in xrange(q):
    c, x, y = map(int, raw_input().split())
    if c == 0:
        uf.unite(x, y)
    else:
        print int(uf.same(x, y))

Solution (Python):
class UnionFindTree:
    """Disjoint-Set Data Structure
       Union-Find Tree
       complexity: 
          init: O(n)
          find, unite, same: O(alpha(n))
       used in SRM505 div.2 900, 
    """
    def __init__(self, n):
        self.par = list(range(n)) 
        self.rank = [0] * n 

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

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

    def same(self, x, y):
        return self.find(x) == self.find(y)
    
N, Q = map(int, input().split())
DisjointSet = UnionFindTree(N)
for _ in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        DisjointSet.unite(x, y)
    elif com == 1:
        print(int(DisjointSet.same(x, y)))

Solution (Python):
class UnionFind:
    def __init__(self):
        self.data = {}
        self.rank = {}

    def make_set(self,x):
        if not x in self.data:
            self.data[x] = x
            self.rank[x] = 0

    def find_set(self,x):
        path = []
        while self.data[x] != x:
            path.append(x)
            x = self.data[x]
        for y in path:
            self.data[y] = x
        return x

    def same(self,x,y):
        if self.find_set(x) == self.find_set(y):
            return True
        else:
            return False

    def unite(self,x,y):
        rx = self.find_set(x)
        ry = self.find_set(y)
        if not rx == ry:
            if self.rank[rx] > self.rank[ry]:
                self.data[ry] = rx
            elif self.rank[rx] < self.rank[ry]:
                self.data[rx] = ry
            else:
                self.data[rx] = ry
                self.rank[rx] += 1

n,q = map(int, raw_input().split(' '))
s = UnionFind()
for i in range(n):
    s.make_set(i)
for i in range(q):
    c,x,y = map(int,raw_input().split(' '))
    if c == 0:
        s.unite(x,y)
    else:
        if s.same(x,y):
            print 1
        else:
            print 0

Solution (Python):



import array


class UnionFind(object):

    def __init__(self, number_of_nodes):
        self.par = array.array("I", range(number_of_nodes))
        self.rank = array.array("I", (0 for i in range(number_of_nodes)))

    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 unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif 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


if __name__ == "__main__":
    n, q = map(int, input().split())
    uf = UnionFind(number_of_nodes=n)
    for i in range(q):
        c, x, y = map(int, input().split())
        if c == 0:
            uf.unite(x, y)
        elif c == 1:
            print(int(uf.in_the_same_set(x, y)))

Solution (Python):
def find(x):
    global set_list
    if set_list[x] == x:
        return x
    result = set_list[x] = find(set_list[x])
    return result


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

while q:
    op, x, y = map(int, input().split())
    if op:
        print(1 if find(x) == find(y) else 0)
    else:
        set_list[find(y)] = find(x)
    q -= 1

Solution (Python):


class UnionFindTree:
    def __init__(self, x):
        self.parent = self
        self.id = x
        self.rank = 0

    def find(self):
        if self.id == self.parent.id:
            return self
        else:
            return self.parent.find()



n, q = map(int, input().split())
nodes = [UnionFindTree(i) for i in range(n)]
for i in range(q):
    com, x, y = map(int, input().split())
    x_root = nodes[x].find()
    y_root = nodes[y].find()
    if com == 0:
        
        if x_root.rank > y_root.rank:
            y_root.parent = x_root
        elif y_root.rank > x_root.rank:
            x_root.parent = y_root
        elif x_root.id != y_root.id:
            y_root.parent = x_root
            x_root.rank += 1
    else:
        
        same = 1 if x_root.id == y_root.id else 0
        print(same)