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:
def find(x):
    if(p[x] == x):return x
    else: 
        p[x] = find(p[x])
        return p[x]
def unite(x,y):
    x = find(x)
    y = find(y)

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

if __name__ == '__main__':
    #start = time.time()
    N,query_num = map(int, input().split())
    union_find_tree = [i for i in range(N)]
    tree_rank = [0]*N
    for i in range(query_num):
        operate,x,y = map(int, input().split())
        if(operate==0):
            unite(union_find_tree,x,y)
        if(operate==1):
            res = same(union_find_tree,x,y)
            if(res):
                print("1")
            else:
                print("0")
    #elapsed_time = time.time() - start
    #print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Accepted

Solution code:


class UnionFind():

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

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

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

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


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

Submission status: Accepted

Solution code:
# Problem A: Disjoint Set: Union Find Tree

_input = '''5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0'''


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

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

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

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


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


uf = UnionFind(N)

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

    # 連結クエリ
    if P == 0:
        uf.union(A, B)
    # 判定クエリ
    else:
        if uf.is_same(A, B):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import collections
import itertools
import operator


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

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

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

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

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

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

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

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

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

Submission status: Accepted

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


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


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

Submission status: Accepted

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

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

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

  def is_same(self, x, y):
    #x と y が同じグループか否か
    return self.find(x) == self.find(y)
#uf=UnionFind(N) uf.union(A,B)のように使う

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

uf = UnionFind(N)
for _ in range(Q):
    P, A, B = map(int, input().split())
    # 連結クエリ
    if P == 0:
        uf.union(A, B)
    # 判定クエリ
    else:
        if uf.is_same(A, B):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys

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

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

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

    def unite(self, x:int, y:int):
        """y を x の属する集合に併合"""
        root_x = self.root(x)
        root_y = self.root(y)
        if root_x == root_y: return
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        elif self.rank[root_x]<self.rank[root_y]:
            root_x,root_y = root_y,root_x
        # 短いほう(y)を長いほう(x)にくっつける
        self.par[root_y] = root_x
        self.size[root_x] += self.size[root_y]
        self.size[root_y] = 0 # もういらない

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

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

Submission status: Accepted

Solution code:
class UnionFindTree:
    '''
    Union Find Tree
    '''

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

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

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

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

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

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


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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:


import collections
import itertools
import operator


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

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

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

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

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


# UnionFind
class UnionFind:
    # 負: ルートで値は木の深さを表す
    # 正: 子で値は次のノードを表す
    def __init__(self, size: int) -> None:
        self.nodes = [-1] * size  # 初期状態では全てのノードがルート

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

    def unite(self, x: int, y: int) -> None:
        root_x, root_y = self.root(x), self.root(y)
        if root_x != root_y:
            if self.nodes[root_x] != self.nodes[root_y]:  # グラフの高さが異なる場合
                # 木のランクが高い方のルートに併合させる
                # 併合後にランクの変動はない
                if self.nodes[root_x] < self.nodes[root_y]:
                    self.nodes[root_y] = root_x
                else:
                    self.nodes[root_x] = root_y
            else:
                # ランクが等しい木同士を併合させるので
                # 併合後は木のランクが1つ上がる
                self.nodes[root_x] += -1
                self.nodes[root_y] = root_x


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

uf = UnionFind(n)
for com, x, y in query:
    if com == 0:  # 連結クエリ
        uf.unite(x, y)
    else:  # 判定クエリ
        if uf.root(x) == uf.root(y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


import collections


class UnitDict(dict):

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

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


class DisjointSetDataStructure(object):

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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

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


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


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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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


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


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

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


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

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

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

    else:
        union(x, y)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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':     # unite
            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:                   # same
            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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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