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.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """頂点xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """頂点xを含む集合と頂点y含む集合を結合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """頂点xと頂点yが同じ集合に属するかどうかを返す"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """頂点xを含む集合の要素数を返す"""
        return -self.parent[self.root(x)]

    def get_cnt(self):
        """集合の個数を返す"""
        return self.cnt


import sys
input = sys.stdin.readline


n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(q)]

uf = UnionFind(n)
ans = []
for i in range(q):
    t, x, y = info[i]
    if t == 0:
        uf.merge(x, y)
        continue
    if uf.is_same(x, y):
        print(1)
    else:
        print(0)

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, num):
    self.rank = [0]*num
    self.par = [i for i in range(num)]
    self.n = num
    self.size = [1]*num
  
  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:
      return 
    if self.rank[x] > self.rank[y]:
      self.par[y] = x
      self.size[x] += self.size[y]
      self.size[y] = 0
    else:
      self.par[x] = y
      self.size[y] += self.size[x]
      self.size[x] = 0
      if self.rank[x] == self.rank[y]:
        self.rank[y] += 1
    
  def same(self, x, y):
    return self.find(x) == self.find(y)
  
  def all_find(self):
    ls = []
    for i in range(len(self.par)):
      ls.append(self.find(i))
    return ls
    
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:
#!python3

import sys
iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, Q = iim()

    S = [[i] for i in range(N)]

    def find(i):
        x = S[i]
        while True:
            k = S[i][0]
            if k == i:
                x[0] = i
                return i
            S[i] = x
            i = k
    def union(i, j):
        ai = find(i)
        aj = find(j)
        if ai != aj:
            S[aj][0] = S[ai][0]
            S[aj] = S[ai]

    def same(i, j):
        ai = find(i)
        aj = find(j)
        return ai == aj

    ans = []
    for com, x, y in (map(int, line.split()) for line in sys.stdin):

        if com == 0:
            union(x, y)
            #print(x, y, *tuple(map(lambda x: (x, hex(id(x))[-4:]), S)))
        elif com == 1:
            ans.append(1 if same(x, y) else 0)
        else:
            raise 1
    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rank = [0]*(n+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_root = self.Find_Root(x)
        y_root = self.Find_Root(y)

        if(x_root == y_root):
            return
        # 違う木に属していた場合rankを見てくっつける方を決める
        if self.rank[x_root] >= self.rank[y_root]:
            self.rank[x_root] += self.rank[y_root]
            self.root[y_root] = x_root
        else:
            self.rank[y_root] += self.rank[x_root]
            self.root[x_root] = y_root

    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return self.rank[self.Find_Root(x)]

tree = UnionFind(n)

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        tree.Unite(x, y)
    else:
        is_same = tree.isSameGroup(x, y)
        print(1 if is_same else 0)

Submission status: Accepted

Solution code:
from collections import deque

class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.member_num = [1 for _ in range(size)]
 
    #representative
    #O(a(N))
    def find(self,x):
        Q = deque()
        while self.table[x] >= 0:
            Q.append(x)
            x = self.table[x]
        while len(Q)>0:
            y = Q.pop()
            self.table[y] = x
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        m1=self.member_num[s1]
        m2=self.member_num[s2]
        if s1 != s2:
            if m1 != m2:
                if m1 < m2:
                    self.table[s1] = s2
                    self.member_num[s2]=m1+m2
                    return [m1,m2]
                else:
                    self.table[s2] = s1
                    self.member_num[s1]=m1+m2
                    return [m1,m2]
            else:
                self.table[s1] = -1
                self.table[s2] = s1
                self.member_num[s1] = m1+m2
                return [m1,m2]
        return [0,0]

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

UF = UnionFind(N)

for i in range(Q):
    c,a,b = list(map(int,input().split()))
    #print(UF.table)
    if c==0:
        UF.union(a,b)
    else:
        if UF.find(a)==UF.find(b):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class UnionFindWithRank(object):
    par = []
    rank = []
    cache = True
    log = []

    def __init__(self, n):
        for i in range(n):
            self.par.append(i)
            self.rank.append(0)

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

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

    def unite(self, x, y):
        ox, oy = x, y
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            x, y = y, x
            self.par[y] = x

        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n, q = map(int, input().split())
u = UnionFindWithRank(n)
for _ in range(q):
    c, a, b= map(int, input().split())
    a, b = a, b
    if c == 0:
        u.unite(a, b)
    else:
        print(1 if u.same(a, b) else 0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''
所要時間は、分位であった。
'''


# ライブラリのインポート
#import re #正規表現
import sys
#import heapq
#import bisect
#import collections
#import math

def main():
    n, q = map(int, input().split())
    P = [i for i in range(n)]
    for line in sys.stdin:
        order = line.strip("\n").split()
        x,y = map(int, order[1:])
        if x > y: x, y = y, x
        while(1):
            x = P[x]
            if x == P[x]: break
        while(1):
            y = P[y]
            if y == P[y]: break
        if order[0] == "0": #unite
            P[x] = P[y] 
        elif order[0] == "1": #same
            print(1) if y == x else print(0)
    


    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self,x):
        root = x
        while self.parents[root] != root:
            root = self.parents[root]
        while self.parents[x] != root:
            parent = self.parents[x]
            self.parents[x] = root
            x = parent
        return root
    def unite(self,x,y):
        xroot,yroot = self.find(x),self.find(y)
        if xroot == yroot:
            return
        xrank,yrank = self.rank[xroot],self.rank[yroot]
        if xrank < yrank:
            self.parents[xroot] = yroot
        elif xrank == yrank:
            self.parents[yroot] = xroot
            self.rank[yroot] += 1
        else:
            self.parents[yroot] = xroot

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(1 if uf.find(x)==uf.find(y) else 0)

Submission status: Accepted

Solution code:
def main():
    n, q = input().split()
    n = int(n)
    q = int(q)
    nums = [i for i in range(n)]
    rank = [0 for i in range(n)]

    def find_top(x):
        if (nums[x] != x):
            nums[x] = find_top(nums[x])
        return nums[x]

    def unite(x, y):
        x = find_top(x)
        y = find_top(y)
        if rank[x] > rank[y]:
            nums[y] = x
        else:
            nums[x] = y
            if (rank[x] == rank[y]):
                rank[y] += 1

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
class UnionFind:
    MAX_N = 0
    PAR  = [] 
    RANK = []

    def __init__(self,n):
        self.MAX_N = 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 union(self,x,y):
        x = self.find(x)
        y = 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())
Ans = []
tree = UnionFind(N+1)
for _ in range(Q):
    t,u,v = map(int,input().split())
    if t == 0:
        tree.union(u,v)
    else:
        if tree.same(u,v):
            Ans.append(1)
        else:
            Ans.append(0)
for a in Ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

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

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

		self.par[x] = y

n, q = MAP()
uf = UnionFind(n)
for _ in range(q):
	com, x, y = MAP()
	if com==0: uf.union(x, y)
	if com==1: print(uf.same(x, y))

Submission status: Accepted

Solution code:




class Node:
    def __init__(self, num):
        self.num = num
        self.parent = self
        self.rank = 0
    
def findSet(node):
    tmp = []
    while node.parent != node:
        tmp.append(node)
        node = node.parent
    
    while tmp:
        tmp.pop().parent = node
    return node

def unite(x, y):
    node1 = findSet(nodes[x])
    node2 = findSet(nodes[y])
    if node1.rank == node2.rank:
        node2.parent = node1
        node1.rank += 1
    elif node1.rank > node2.rank:
        node2.parent = node1
    else:
        node1.parent = node2

def same(x, y):
    node1 = findSet(nodes[x])
    node2 = findSet(nodes[y])
    return node1.parent == node2.parent

nums=list(map(int,input().split()))
n = nums[0]
q = nums[1]

nodes = []
for i in range(n):
    nodes.append(Node(i))

for i in range(q):
    nums=list(map(int,input().split()))
    if nums[0] == 0:
        unite(nums[1], nums[2])
    else:
        if same(nums[1], nums[2]):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:

class UnionFind:

  def __init__(self, n):
    self.n = n

    # parentsの値を木の高さ判定につかっている
    # rankやsizeをつかって木の高さ判定をすることは一般的に多いが、もっとスマートな形
    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]: # parentsの値を木の高さ判定につかっている
      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):
    x = self.find(x)
    y = self.find(y)

    print(1 if x == y else 0)

  
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)
  else:
    uf.same(x, y)

Submission status: Accepted

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

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

	def make(self, n):
		for i in range(n):
			self.parent[i] = i

	def unite(self, x, y):
		xroot = self.findset(x)
		yroot = self.findset(y)
		if self.rank[xroot] < self.rank[yroot]:
			self.parent[xroot] = yroot
		elif self.rank[xroot] > self.rank[yroot]:
			self.parent[yroot] = xroot
		else:
			self.parent[xroot] = yroot
			self.rank[yroot] += 1
			node = y
			while True:
				self.rank[node] += 1
				if self.parent[node] == node:
					break
				node = self.parent[node]
			self.rank[y] += 1

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

def main():
	n, q = map(int, input().strip().split())
	uf = UnionFind(n)
	for i in range(q):
		com, x, y = map(int, input().strip().split())
		if com == 0:
			uf.unite(x, y)
		else:
			xroot = uf.findset(x)
			yroot = uf.findset(y)
			# print("xr: {} yr: {}".format(xroot, yroot))
			if xroot == yroot:
				print("1")
			else:
				print("0")

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
class unionfind:
  def __init__(self, n):
    self.data = [ -1 for i in range(n) ]
    
  def root(self, x):
    if self.data[x] < 0:
      return x
    else:
      self.data[x] = self.root(self.data[x])
      return self.data[x]
    
  def same(self, l, r):
    return self.root(l) == self.root(r)
  
  def join(self, l, r):
    l = self.root(l)
    r = self.root(r)
    if l == r:
      return False
    if self.data[l] > self.data[r]:
      l, r = r, l
    self.data[l] += self.data[r]
    self.data[r] = l
    return True
  
n,q,*l = map(int,open(0).read().split())
uf = unionfind(n)
for c,x,y in zip(*[iter(l)]*3):
  if c:
    print(int(uf.same(x,y)))
  else:
    uf.join(x,y)

Submission status: Accepted

Solution code:

class DisjointSet:

    def __init__(self, n):
        self.p = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

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

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

    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.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

def main():
    n, q = map(int, input().split(' '))

    ds = DisjointSet(n)

    for _ in range(q):
        c, a, b = map(int, input().split(' '))
        
        if c == 0:
            ds.unite(a, b)
        else:
            if ds.same(a, b):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


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

    def find(self, x):
        if self.parent[x] != x:
            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 x != y:
            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 have_same_root(self, x, y):
        return self.find(x) == self.find(y)


if __name__ == "__main__":
    n_node, n_command = map(int, input().split())
    uf_tree = UnionFindTree(n_node)

    for command, x, y in (map(int, i.split()) for i in sys.stdin):
        if command == 0:
            uf_tree.unite(x, y)
        else:
            print(int(uf_tree.have_same_root(x, y)))

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/all/DSL_1_A
# AtCoderの解説がわかりやすい https://youtu.be/zV3Ul2pA2Fw?t=1425
# この解説を見た上で本を読むとより理解が深まる

# 本とはやや違う実装だがこちらのほうがスマート(だとおもってる)


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。
        # rankは親ノードの負の数の大きさに対応している

    def root(self, A):  # 本で言うfindset
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):  # 本で言うrank
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


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

Submission status: Accepted

Solution code:
# DLS_1_A Disjoint Set: Union Find Tree
import sys
n, q = map(int, input().split())


class Dset:
    def __init__(self, value):
        self.value = value
        self.rank = 0
        self.parent = self

    def unite(self, y):
        x = self
        while x.parent != x:
            x = x.parent
        while y.parent != y:
            y = y.parent

        if x.rank >= y.rank:
            big = x
            small = y
        else:
            big = y
            small = x

        small.parent = big.parent
        small.rank += 1
        return

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


l = [] * n
for i in range(n):
    l.append(Dset(i))

for i in range(q):
    com, x, y = map(int, sys.stdin.readline().strip().split())
    if com == 0:
        l[x].unite(l[y])
    else:
        print(l[x].same(l[y]))

# for i in range(n):
#     print('i : {}  parent : {}'.format(i, l[i].parent.value))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

def find(x):
    if p[x] == x:
        return x
    else:
        p[x] = find(p[x])
        return p[x]

def unite(x, y):
    px, py = find(x), find(y)
    p[px] = py

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

Submission status: Accepted

Solution code:
from typing import List

class UnionFind:
	def __init__(self, V: int) -> None:
		self.V: int = V
		self.pi: List[int] = [i for i in range(V)]
		self.rank: int = [0 for _ in range(V)]

	def findSet(self, x: int) -> int:
		if x != self.pi[x]:
			self.pi[x] = self.findSet(self.pi[x])
		return self.pi[x]

	def same(self, x: int, y: int) -> bool:
		return self.findSet(x) == self.findSet(y)

	def link(self, x: int, y: int) -> None:
		if self.rank[x] > self.rank[y]:
			self.pi[y] = x
		else:
			self.pi[x] = y
			if self.rank[x] == self.rank[y]:
				self.rank[y] += 1

	def unite(self, x: int, y: int) -> None:
		self.link(self.findSet(x), self.findSet(y))


if __name__ == "__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:
			if UF.same(x, y):
				print(1)
			else:
				print(0)

Submission status: Accepted

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

class UnionFindTree:
    def __init__(self, n: int):
        self.n = n
        self.root = [-1] * (n+1)
        self.rank = [0] * (n+1)
    def findRoot(self, x: int) -> int:
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.findRoot(self.root[x])
            return self.root[x]
    def unite(self, x: int, y: int):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    def same(self, x: int, y: int) -> bool:
        if self.findRoot(x) == self.findRoot(y):
            return True
        else:
            return False
    def count(self, x: int) -> int:
        return -self.root[self.findRoot(x)]


def main():
    n, q = map(int, input().split())
    UFT = UnionFindTree(n-1)
    for _ in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            UFT.unite(x, y)
        else:
            if UFT.same(x, y):
                print(1)
            else:
                print(0)


if __name__ == '__main__': main()

Submission status: Accepted

Solution code:
class UnionFindTree:
  def __init__(self, n: int):
    self.__parent = [i for i in range(n)]
    self.__rank = [0 for i in range(n)]

  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)

  def __find_set(self, x):
    if x != self.__parent[x]:
      self.__parent[x] = self.__find_set(self.__parent[x])
    return self.__parent[x]

  def __link(self, x, y):
    if self.__rank[x] < self.__rank[y]:
      self.__parent[x] = y
    else:
      if self.__rank[x] == self.__rank[y]:
        self.__rank[x] += 1
      self.__parent[y] = x


N, Q = map(int, input().split())
t = UnionFindTree(N)
for i in range(Q):
  command, x, y = map(int, input().split())
  if command == 0:
    t.unite(x, y)
  if command == 1:
    if t.same(x, y):
      print(1)
    else:
      print(0)

Submission status: Accepted

Solution code:
# AOJ DSL_1_A
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A

import sys

line = input()
n, q = list(map(int, line.split()))
rel = {}
for i in range(0, n):
    rel[i] = []
parent = [i for i in range(0, n)]

def find(x):
    if parent[x] == x:
        return x
    else:
        y = find(parent[x])
        parent[x] = y
        return y

def unite(x, y):
    rx = find(x)
    ry = find(y)
    if rx < ry:
        parent[ry] = rx
    else:
        parent[rx] = ry

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

for _ in range(0, q):
    line = input()
    query, x, y = list(map(int, line.split()))
    if query == 0:
        unite(x, y)
    elif query == 1:
        print(1 if same(x, y) else 0)

Submission status: Accepted

Solution code:

def init(N, parent, rank):
    for i in range(N):
        parent.append(i)
        rank.append(0)
    return parent, rank

def find(parent, v):
    if parent[v] == v:
        return v
    else:
        parent[v] = find(parent, parent[v])
        return parent[v]

def unite(parent, rank, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a == b:
        return 
    elif rank[a] < rank[b]:
        parent[a] = b
        return parent
    elif rank[a] > b:
        parent[b] = a
        return parent
    else:
        parent[b] = a
        rank[a] += 1
        return parent, rank

def union_find():
    N, Q = [int(i) for i in input().split()]
    parent = []
    rank = []
    init(N, parent, rank)
    for i in range(Q):
        P, A, B = [int(i) for i in input().split()]
        if P == 0:
            unite(parent, rank, A, B)
        else:
            a = find(parent, A)
            b = find(parent, B)
            if a == b:
                print("1")
            else:
                print("0")

if __name__ == "__main__":
    union_find()

Submission status: Accepted

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

def same(node_a, node_b):
    if node_a.root() == node_b.root():
        return True
    else:
        return False

def unite(node_a, node_b):
    root_a = node_a.root()
    root_b = node_b.root()
    if root_a == root_b:
        return False
    if root_b.depth > root_a.depth:
        root_a, root_b = root_b, root_a
    root_b.is_root = False
    root_b.parent = root_a
    root_a.depth = max(root_a.depth, root_b.depth+1)
    return True

class Node:
    def __init__(self):
        self.is_root = True
        self.parent = None
        self.depth = 1
    
    def root(self):
        node = self
        while not node.is_root:
            node = node.parent
        return node

def main():
    n, q = map(int, input().split())

    nodes = [Node() for i in range(n)]

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

def solve():
	n,q,*l = map(int,open(0).read().split())
	uf = UnionFind(n)
	for c,x,y in zip(*[iter(l)]*3):
		if c:
			print(0 + uf.isSame(x,y))
		else:
			uf.unite(x,y)
            
if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
class Union_find():
    def __init__(self, N):
        self.Group = [i for i in range(N)]
        
    def find(self,x):# find(a)=find(b)のとき同じグループ
        while self.Group[x] != x:
            x = self.Group[x]
        return x

    def Union(self,x,y):  # xとyが同じグループになるよう更新
        if self.find(x) != self.find(y):
            self.Group[self.find(y)] = self.Group[self.find(x)] = min(self.find(y),self.find(x))
    
    
N,q = map(int,input().split())
A = Union_find(N)

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

    if com == 0:
        A.Union(x,y)

    else:
        if A.find(x) == A.find(y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
n,q = map(int, input().split( ))
tag = [i for i in range(n)]
for _ in range(q):
    cmmd,x,y =map(int, input().split( ))
    if cmmd == 0:
        chng1 = []
        chng2 = []
        chng1.append(x)
        x = tag[x]
        chng2.append(y)
        y = tag[y]
        while x != tag[x]:
            chng1.append(x)
            x = tag[x]
        chng1.append(x)
        while y != tag[y]:
            chng2.append(y)
            y = tag[y]
        chng2.append(y)
        if x != y:
            if len(chng1) < len(chng2):
                for x_ in chng1:
                    tag[x_] = y
            else:
                for y_ in chng2:
                    tag[y_] = x
 
    else:
        while x != tag[x]:
            x = tag[x]
        while y != tag[y]:
            y = tag[y]
        if x != y:
            print(0)
        else:
            print(1)