Problem:


Disjoint Set

Write a program which manipulates a disjoint set S = {S1, S2, . . . , Sk}.

First of all, the program should read an integer n, then make a disjoint set where each element consists of 0, 1, ... n&minus;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 Sx and Sy, into a new set.

same(x, y): determine whether x and y are in the same set.

Input

n q
com1 x1 y1
com2 x2 y2
...
comq xq yq

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 &ne; 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



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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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):
        # compression of the path
        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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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):
        # compression of the path
        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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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):
        # compression of the path
        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)

Submission status: Accepted

Solution code:
#coding:utf-8
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)] #基準(par = parentのpar)
    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))

#計算量O(logn)経路圧縮とrankを用いた計算量
#-経路圧縮：葉から根へたどる際に通過したノードの親ポインタを根にする
#-rank：木を合併する際に、ノードの高さの高い方に低い方が結合しにいく

#処理の流れ
#same:  入力受け取り→親が同じ？→true/false
#unite: 高さがどっちが高いか？→高い方へ結合

Submission status: Accepted

Solution code:
#  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=jp
#  Disjoint Set: Union Find Tree : python3
#  2018.12.23 yonezawa

#from collections import deque
import sys
input = sys.stdin.readline
#import cProfile
#from math import cos,sin,radians,sqrt
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())
        #print (a,b,c)
        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()
    #pr = cProfile.Profile()
    #pr.runcall(main)
    #pr.print_stats()

Submission status: Accepted

Solution code:
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:
        # unite
        uf.unite(uf.nodes[ix], uf.nodes[iy])
    else:
        # same
        print(1 if uf.bool(uf.nodes[ix], uf.nodes[iy]) else 0)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

# Union-Find木
class UnionFind:
    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        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]
            # 木の高さが同じなら片方を1増やす
            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))
        # グループ0の分を引いて返却
        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)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

"""
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): # Union Find
    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)] # pointer
rank = [0 for i in range(n)]
for i in range(q):
    com, x, y = map(int,raw_input().split())
    if com: # same
        isSameSet(x, y, p, rank)
    else: # unite
        union(x, y ,p , rank)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)) # parent
        self.rank = [0] * n # depth of tree

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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


# main
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:
        # union
        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
        same = 1 if x_root.id == y_root.id else 0
        print(same)

Submission status: Accepted

Solution code:
class node:
    def __init__(self,parent):
        self.parent=parent

def findset(x):
    global nodes
    if nodes[x].parent==x:
        return x
    else:
        nodes[x].parent=findset(nodes[x].parent)
        return nodes[x].parent

def unite(x,y):
    global rank,nodes
    findset(x)
    findset(y)
    if rank[nodes[x].parent]<rank[nodes[y].parent]:
        nodes[nodes[x].parent].parent=nodes[nodes[y].parent].parent
    elif rank[nodes[x].parent]==rank[nodes[y].parent]:
        nodes[nodes[x].parent].parent=nodes[nodes[y].parent].parent
        rank[y]+=1
    else:
        nodes[nodes[y].parent].parent=nodes[nodes[x].parent].parent

def same(x,y):
    global nodes
    findset(x)
    findset(y)
    if nodes[x].parent==nodes[y].parent:
        print(1)
    else:
        print(0)

n,q=map(int,raw_input().split())
rank=[0]*n
nodes=[]
for i in xrange(n):
    fac=node(i)
    nodes.append(fac)
for i in xrange(q):
    com,x,y=map(int,raw_input().split())
    if com==0:
        unite(x,y) 
    else:
        same(x,y)

Submission status: Accepted

Solution code:
n, q = map(int, raw_input().split())
parent = range(n)
def root(x):
    if x == parent[x]:
        return x
    return root(parent[x])
def unite(x, y):
    rx = root(x); ry = root(y)
    if rx < ry:
        parent[ry] = rx
    elif ry < rx:
        parent[rx] = ry
def same(x, y):
    print (root(x) == root(y))*1

for i in xrange(q):
    com, x, y = map(int, raw_input().split())
    [unite,same][com](x, y)