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:
class UnionFind():
    def __init__(self, n):
        self.n=n
        self.parents=[-1]*n #各要素の親要素の番号を格納するリスト

    def find(self, x): #要素xが属するグループの根を返す
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]

    def union(self,x,y): #要素xが属するグループと要素yが属するグループとを併合する
        x=self.find(x)
        y=self.find(y)

        if x==y:
            return

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

        self.parents[x]+=self.parents[y]
        self.parents[y]=x

    def size(self,x): #要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def same(self,x,y): #要素x, yが同じグループに属するかどうかを返す
        return self.find(x)==self.find(y)

    def members(self,x): #要素xが属するグループに属する要素をリストで返す
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]

    def roots(self): #すべての根の要素をリストで返す
        return [i for i, x in enumerate(self.parents) if x<0]

    def group_count(self): #グループの数を返す
        return len(self.roots())

    def all_group_members(self): #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

#print(list(uf.all_group_members().values())) #グループ一覧を表示

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

Submission status: Accepted

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


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)  # -1ならそのノードが根,で絶対値が木の要素数
        self.rank = [0] * (n + 1)

    def find(self, x):  # xの根となる要素番号を返す
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

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

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

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


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

Submission status: Accepted

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

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

parents = [-1] * n

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

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

    if x == y:
        return

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

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    # この時点でそれぞれのノードは自分を親としている
    # 初期化時に問題が0の頂点を認めるかに注意すること
    def __init__(self, n):
        self.N = n
        self.parent = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    # xの根を返す関数
    def root(self, x):
        visited_nodes = []
        while True:
            p = self.parent[x]
            if p == x:
                # 縮約
                for node in visited_nodes:
                    self.parent[node] = x
                return x
            else:
                visited_nodes.append(x)
                x = p

    # 木の結合を行う。親の配下に入る
    def unite(self, x, y):
        if not self.root(x) == self.root(y):
            if self.rank[x] > self.rank[y]:
                self.parent[self.root(y)] = self.root(x)
            else:
                self.parent[self.root(x)] = self.root(y)
                if self.rank[x] == self.rank[y]:
                    self.rank[self.root(y)] += 1

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

    # 木の根に到達すまでにたどるノードの配列を返す
    def printDebugInfo(self):
        print([self.root(i) for i in range(self.N)])


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

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():
    class UnionFind(object):
        def __init__(self, n=1):
            # 木の親要素を管理するリストparをつくります。
            # par[x] == xの場合には、そのノードが根であることを示します。
            # 初期状態では一切グループ化されていないので、すべてのノードが根になりますね。
            self.par = [i for i in range(n)]
            # 木の高さを持っておき、あとで低い方を高い方につなげる。初期状態は0
            self.rank = [0 for _ in range(n)]
            self.size = [1 for _ in range(n)]

        def find(self, x):
            """
            x が属するグループを探索：
            ある２つの要素が属する木の根が同じかどうかをチェックすればよい。
            つまり、親の親の親の・・・と根にたどり着くまで走査すればよい。
            再帰。
            """
            # 根ならその番号を返す
            if self.par[x] == x:
                return x
            # 根でないなら、親の要素で再検索
            else:
                # 一度見た値については根に直接繋いで経路圧縮
                # 親を書き換えるということ
                self.par[x] = self.find(self.par[x])
                return self.par[x]

        def union(self, x, y):
            """
            x と y のグループを結合
            """
            # 根を探す
            x = self.find(x)
            y = self.find(y)
            # 小さい木に結合して経路圧縮
            if x != y:
                if self.rank[x] < self.rank[y]:
                    x, y = y, x
                # 同じ長さの場合rankが1増える
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                # 低い方の木の根を高い方の根とする
                self.par[y] = x
                self.size[x] += self.size[y]

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

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

    N, Q = map(int, input().split())
    uf = UnionFind(N)  # ノード数Nでクラス継承

    for i in range(Q):
        # A,Bはノード
        P, A, B = map(int, input().split())
        if P == 0:
            # 連結クエリ union
            uf.union(A, B)
        else:
            # 判定クエリ find
            if uf.is_same(A, B):
                print(1)
            else:
                print(0)


resolve()

Submission status: Accepted

Solution code:
from collections import deque

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

(n, q) = get_input()

d = [] # [{i} for i in range(n)]

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

Submission status: Accepted

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
# 同一の集合の判定
def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False
# 集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

# 集合の数
def uCnt(x):
    return -par[find(x)]

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

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

Submission status: Accepted

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

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

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

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

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

    def findSet(self, x):
        # Recursively invoke findSet() until it reaches to the parent (root)
        if x != self.parent[x]:
            self.parent[x] = self.findSet(self.parent[x])
        return self.parent[x]


import sys
# sys.stdin = open('input.txt')

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n + 1)

    # 探索
    # 根ならその場号を返す
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換えていく（パス圧縮）
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)


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

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
            
    n,q = LI()
    rank = [0]*n
    par = [i for i in range(n)]
    for _ in range(q):
        c,x,y = LI()
        x -= 1
        y -= 1
        if not c:
            if root(x) != root(y):
                unite(x,y)
        else:
            print([0,1][root(x) == root(y)])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


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

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


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

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, n):
        #親の番号
        self.par = list(range(n))

    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 unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        #結合する
        self.par[y] = x

    def same(self, x, y):
        #xとyが同じ集合に属するか
        #return 1 if self.root(x) == self.root(y) else 0
        #print(x,self.root(x), " : ", y,self.root(y))
        print(1) if self.root(x) == self.root(y) else print(0)

def querying(queries, uft):
    for query in queries:
        if query[0] == 0:#unite
            uft.unite(query[1], query[2])
        else:
            uft.same(query[1], query[2])
        #print(uft.par)
if __name__ == '__main__':
    n, q = map(int, input().split())
    queries = [list(map(int, input().split())) for i in range(q)]
    #instant UnionFindTree
    uft = UnionFindTree(n)
    #Querying
    querying(queries, uft)

Submission status: Accepted

Solution code:
import sys,queue,math as np
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
LI = lambda : [int(x) for x in input().split()]

N,Q = LI()
g = [i for i in range(N)]

def root(x):
    if x == g[x] : return x
    g[x] = root(g[x])
    return g[x]

for _ in range(Q):
    c,x,y = LI()
    if c == 0:
        g[root(x)] = root(y)
    else:
        print (int(root(x) == root(y)))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in 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 same(self, x, y):
        return self.find(x) == self.find(y)

    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

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

sets = UnionFind(n)
for _ in range(q):
    l = list(map(int, input().split()))
    if l[0] == 0:
        sets.union(l[1], l[2])
    else:
        if(sets.same(l[1], l[2])):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class Unionfind():

    def __init__(self, n):
        self.par = [-1]*n

    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 same(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.par[x]>self.par[y]:
            x,y = y,x
        self.par[x]+=self.par[y]
        self.par[y] = x
        return True

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

    def count_group():
        c = 0
        for i in range(len(self.par)):
            if self.par[i]<0:
                c+=1
        return c

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

Submission status: Accepted

Solution code:
class UnionFind:
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rnk = [0]*(n+1)
		self.Maxroot = -1

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

	def Unite(self, x, y):
		x = self.Find_Root(x)
		y = self.Find_Root(y)
		if x == y:
			return 
		elif self.rnk[x] > self.rnk[y]:
			self.root[x] += self.root[y]
			if self.root[x] < self.Maxroot:
				self.Maxroot = self.root[x]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			if self.root[y] < self.Maxroot:
				self.Maxroot = self.root[y]
			self.root[x] = y
			if self.rnk[x] == self.rnk[y]:
				self.rnk[y] += 1

	def isSameGroup(self, x, y):
		return self.Find_Root(x) == self.Find_Root(y)

	def Count(self, x):
		return self.root[self.Find_Root(x)] * (-1)


N, Q = map(int, input().split())
solve = UnionFind(N)
ans = []
for _ in range(Q):
	q,x,y = map(int, input().split())
	if q == 0:
		solve.Unite(x,y)
	else:
		ans.append(solve.isSameGroup(x,y))

for a in ans:
	if a:
		print(1)
	else:
		print(0)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1] * (n + 1)
        self.size = [1] * (n + 1)

    def root(self, idx):
        if self.par[idx] == -1:
            return idx

        self.par[idx] = self.root(self.par[idx])
        return self.par[idx]

    def unite(self, idx1, idx2):
        idx1_par = self.root(idx1)
        idx2_par = self.root(idx2)

        if idx1_par == idx2_par:
            return

        if self.size[idx1_par] >= self.size[idx2_par]:
            self.size[idx1_par] += self.size[idx2_par]
            self.par[idx2_par] = idx1_par
        else:
            self.size[idx2_par] += self.size[idx1_par]
            self.par[idx1_par] = idx2_par

    def same(self, idx1, idx2):
        return self.root(idx1) == self.root(idx2)


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

uf = UnionFind(n)

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

Submission status: Accepted

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

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

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

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

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

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n = n #今後も使う値、基本的には全て、self.n に代入する
    self.parents = [-1]*n # -1 で初期化
  def unite(self,x,y):
    x = self.find(x)
    y = self.find(y)
    if x == y: return
    if self.parents[x] > self.parents[y]:
      x,y = y,x
    
    self.parents[x] += self.parents[y]
    self.parents[y] = x
  def find(self,x):#rootを見つける
    if self.parents[x] < 0:
      return x
    else:
      #縮約
      self.parents[x] = self.find(self.parents[x])#再帰！親のさらにnodeを辿った値に更新する。
      return self.parents[x]
      #縮約なしver
      # return self.find(self.parents[x])
  def same(self,a,b):
    return self.find(a) == self.find(b)
if __name__ == "__main__":
  n,q = map(int,input().split())
  uf = UnionFind(n)
  for i in range(q):
    com,x,y = map(str,input().split())
    x = int(x)
    y = int(y)
    if com == "0": 
      uf.unite(x,y)
      #print(uf.parents,i)
    if com == "1": 
      if uf.same(x,y): print(1)
      else: print(0)
  #print(uf.parents)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
parent=list(range(n))
rank=[0]*n
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]<rank[ry]:
		parent[rx]=ry
	else:
		parent[ry]=rx
		if rank[rx]==rank[ry]:
			rank[rx]+=1
for i in range(q):
	c,a,b=map(int,input().split())
	if c==0:
		unite(a,b)
	else:
		if same(a,b):
			print(1)
		else:
			print(0)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline

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

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

"""
uniteでまとめ、findで見つける。
n(要素数)だけ最初に付け加えること。
"""

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

Submission status: Accepted

Solution code:
# Disjoint Set
# https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_A


class UnionFind:
    __slots__ = ["_size", "_first_index", "_parents"]

    def __init__(self, size: int, is_zero_indexed: bool = True) -> None:
        self._size = size
        self._first_index = 0 if is_zero_indexed else 1
        self._parents = [-1] * (size + self._first_index)

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self._parents[x] > self._parents[y]:
            x, y = y, x
        self._parents[x] += self._parents[y]
        self._parents[y] = x

    def get_size(self, x: int) -> int:
        """Get the size of the group vertex x belongs"""
        return -self._parents[self.find(x)]

    @property
    def groups(self) -> int:
        """Return the number of groups."""
        return len({self.find(x) for x in range(self._first_index, self._size + self._first_index)})


def main():
    N, Q = map(int, input().split())
    uf = UnionFind(N)
    ans = []
    for _ in range(Q):
        com, x, y = map(int, input().split())
        if com:
            ans.append(uf.is_same(x, y) * 1)
        else:
            uf.unite(x, y)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1 for _ in range(n)]

    def unite(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        if self.size(root_x) < self.size(root_y):
            root_x, root_y = root_y, root_x
        self.parents[root_x] += self.parents[root_y]
        self.parents[root_y] = root_x
        return True

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

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

def main():
    n, q = LI()
    uf = UnionFind(n)
    ans = []
    for _ in range(q):
        com, x, y = LI()
        if com == 0:
            uf.unite(x, y)
        if com == 1:
            if uf.same(x, y):
                ans.append(1)
            else:
                ans.append(0)
    for a in ans:
        print(a)

main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.par =[-1 for i in range(N)]
    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 unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.par[x] > self.par[y]:
            x,y = y,x
        self.par[x] +=self.par[y]
        self.par[y] = x

    def size(self,x):
        return -self.par[self.find(x)]
    def same(self,x,y):
        return self.find(x)==self.find(y)

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

Submission status: Accepted

Solution code:
# Disjoint Set: Union Find Tree
class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 最初は全てが根であるとして初期化        
        self.parent = [-1] * N  # idxが各ノードのid, 値がそのノードの親ノードのid
        self.rank = [0] * N # idxが各ノードのid, 値がそのノードの集合における高さ

    def root(self, x):  # ノードのidを受け取って一番上の親ノードのidを帰す
        if (self.parent[x] < 0):
            return x
        self.parent[x] = self.root(self.parent[x])  # 経由したノードすべての親を上書き（経路圧縮）
        return self.parent[x]

    def unite(self, x, y): # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        rx = self.root(x) # xの根をrx
        ry = self.root(y) # yの根をry
        if (rx == ry): # xとyの根が同じ(=同じ木にある)時はそのまま
            return False

        if (self.rank[rx] > self.rank[ry]): # 高い方に低い方をつなぐ
            self.parent[ry] = rx
        else:
            self.parent[rx] = ry
            if (self.rank[rx] == self.rank[ry]):
                self.rank[ry] += 1

        return True

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

N, Q = map(int, input().split())
ds = UnionFind(N)
for _ in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        # unite
        ds.unite(x, y)
    elif com == 1:
        # same?
        print(1 if ds.same(x, y) else 0)