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):
    global s
    if s[x] == x:
        return x
    s[x] = find(s[x])
    return s[x]

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

s =[i for i in range(n)]

for i in range(q):
    com, x, y = map(int, input().split())
    if com:
        if find(x) == find(y): print(1)
        else: print(0)
    else:
        s[find(y)] = find(x)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)
 
N, Q = tuple(map(int, input().split()))
 
tree = [[-1, 1]  for _ in range(N)] # [next, rank]
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
 
def unite(x, y):
    px = find(x)
    py = find(y)
     
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
 
for _ in range(Q):
    com, x, y = tuple(map(int, input().split()))
    if com: # same
        print(int(find(x) == find(y)))
    else: # unite
        if not int(find(x) == find(y)):
            unite(x, y)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
class DisjointSet():
    def __init__(self, size):
        self.size = size
        self.rank = [None] * size
        self.parents = [None] * size
        for i in range(size):
            self.makeSet(i)

    def makeSet(self, x):
        self.parents[x] = x
        self.rank[x] = 0

    def findSet(self, x):
        if x != self.parents[x]:
            self.parents[x] = self.findSet(self.parents[x])
        return self.parents[x]

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


if __name__ == '__main__':

    n, q = [int(s) for s in input().split(" ")]
    com = [list(map(int, input().split(" "))) for _ in range(q)]
    ds = DisjointSet(n)

    for c, x, y in com:
        if c == 0:
            ds.unite(x, y)
        else:
            print(int(ds.same(x, y)))

Submission status: Accepted

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

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

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

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


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

Submission status: Accepted

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

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

    def merge(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        elif self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            self.rank[y] += 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.merge(x, y)
    else:
        print(1 if uf.same(x, y) else 0)

Submission status: Accepted

Solution code:
import sys

def findset(x,element):
    if(x != element[x]):
        element[x] = findset(element[x],element)
    return element[x]

def union(x,y,rank,element):
    link(findset(x,element),findset(y,element),rank,element)

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

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

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

for i in range(q):
    query,x,y = map(int, input().split());
    if(query == 0):
        union(x,y,rank,element)
    else :
        if(findset(x,element) == findset(y,element)):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:

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

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

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

def union(x, y):
 link(findSet(x), findSet(y))

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

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


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

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

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


output = []

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

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

for ans in output:
 print(ans)

Submission status: Accepted

Solution code:
# Disjoint Set: Union Find Tree
p = []
rank = []

def makeSet(x):
    global p, rank
    p.append(x)
    rank.append(0)

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

def link(x, y):
    global p, rank
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1

def union(x, y):
    link(findSet(x), findSet(y))    

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

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

for i in range(q):
    [com, x, y] = list(map(int, input().split()))
    if com == 0:
        union(x, y)
    else:
        print(same(x, y))

Submission status: Accepted

Solution code:

def union(x, y):
    link(findSet(x), findSet(y))

def link(x, y):
    if r[x] > r[y]:
        p[y] = x
    else:
        p[x] = y
        if r[x] == r[y]: r[y] = r[y] + 1

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


if __name__ == '__main__':

    p = [];
    r = [];

    n_set, n_quare = map(int, input().split())

    for i in range(n_set):
        p.append(i)
        r.append(0)


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

        if q == 0:
            union(x, y)

        else:
            print(int(findSet(x) == findSet(y)))

Submission status: Accepted

Solution code:
n, nq = map(int, input().split())
set_list = list(range(n))

def find(n):
    global set_list
    if set_list[n] == n:
        return n
    result = set_list[n] = find(set_list[n])
    return result

def same(x, y):
    set_list[find(y)] = find(x)

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

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

Submission status: Accepted

Solution code:
#! python3
# disjoint_set_union_find_tree.py

n, q = [int(x) for x in input().split(' ')]

sets = [set([i]) for i in range(n)]

def unite(Sx, Sy):
    return Sx | Sy

def search(x):
    global sets
    flag = False
    for i in range(len(sets)):
        if x in sets[i]:
            flag = True
            break
    if flag:
        return i
    else:
        return None

def same(x, y):
    global sets
    flag = 0
    for set in sets:
        if x in set:
            if y in set:
                 flag = 1
            break
    return flag

for i in range(q):
    query, x, y = input().split(' ')
    x, y = int(x), int(y)
    if query == '0':
        # unite
        i_x = search(x)
        i_y = search(y)
        if i_x != None and i_y != None and i_x != i_y:
            sets[i_x] = unite(sets[i_x], sets[i_y])
            del sets[i_y]
    elif query == '1':
        # same
        print(same(x, y))

Submission status: Accepted

Solution code:
#! python3
# disjoint_set_union_find_tree.py

class UnionFindTree():
    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.find(self.par[x])

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

n, q = [int(x) for x in input().split(' ')]
uft = UnionFindTree(n-1)

for i in range(q):
    com, x, y = [int(x) for x in input().split(' ')]
    if com == 0:
        uft.unite(x, y)
    elif com == 1:
        if uft.same_check(x, y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys


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

    def find(self, vertex):
        if self.dat[vertex] is vertex: return vertex
        self.dat[vertex] = self.find(self.dat[vertex])
        # print("searching : " + str(vertex))
        return self.dat[vertex]

    def merge(self, child, parent):
        """
        parentとchildをマージして、parentの所属にする
        :param parent:
        :param child:
        :return:
        """
        self.dat[self.find(child)] = self.dat[self.find(parent)]

    def is_same(self, v, w):
        """
        頂点vと頂点wが同じ集合に所属しているか
        :param v:
        :param w:
        :return:
        """
        return self.find(v) == self.find(w)


n, q = map(int, input().split())
uni = UnionFind(n)
sys.setrecursionlimit(114514)
while q > 0:
    q -= 1
    com, x, y = map(int, input().split())
    if com is 0:
        uni.merge(x, y)
    else:
        print(1 if uni.is_same(x, y) else 0)

Submission status: Accepted

Solution code:

class UnionFindTree:

    def __init__(self):
        self.cnt = []
        self.par = []

    def add(self, n):
        assert n == len(self.par), "Invalid Value"
        self.par.append(n)
        self.cnt.append(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:
            cnt = self.cnt[x] + self.cnt[y]
            self.cnt[x] = cnt
            self.cnt[y] = cnt
            if x < y:
                self.par[y] = x
            else:
                self.par[x] = y

    def size(self, x):
        x = self.root(x)
        return self.cnt[x]


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
import itertools
import operator
import sys


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

        self.parent = KeyDict()
        self.rank = collections.defaultdict(int)

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

    def grouper(self):
        parent_getter = operator.itemgetter(1)
        for _, group in itertools.groupby(
                sorted(self.parent.items(), key=parent_getter), parent_getter):
            yield [i for i, _ in group]


sys.stdin.readline()
uf = UnionFind()
for line in sys.stdin:
    com, x, y = map(int, line.split())
    if com == 0:
        uf.unite(x, y)
    elif com == 1:
        print(1 if uf.are_same(x, y) else 0)

Submission status: Accepted

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


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)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        uf.union(x, y)
    else:
        if uf.is_same(x, y):
            print(1)
        else:
            print(0)

Submission status: Accepted

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

root_list = [i for i in range(n)]

def root(x):
    path_to_root = []
    while root_list[x] != x:
        path_to_root.append(x)
        x = root_list[x]
    for node in path_to_root:
        root_list[node] = x
    return x

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

def unite(x,y):
    root_list[root(x)] = root(y)

for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        #unite
        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().split())
lines = [list(map(int, input().split())) for i in range(q)]
set = []
c = 0
index = [-i-1 for i in range(n)]
for line in lines:
	if line.pop(0) == 0:#or
		index_a = index[line[0]]
		index_b = index[line[1]]
		if index_a < 0 and index_b < 0:
			set += [line]
			index[line[0]] = c
			index[line[1]] = c
			c += 1
		elif index_a < 0:
			set[index_b] += [line[0]]
			index[line[0]] = index_b
		elif index_b < 0:
			set[index_a] += [line[1]]
			index[line[1]] = index_a
		elif index_a == index_b:
			continue
		else:
			set[index_a] += set[index_b]
			for i in set[index_b]:
				index[i] = index_a
		
	else:#check
		if index[line[0]] == index[line[1]]:
			print(1)
		else:
			print(0)

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
group = [[i] for i in range(n)]
key = [i for i in range(n)]
for j in range(q):
    com, x, y = map(int, input().split())
    if com == 1:
        if key[x] == key[y]:
            print(1)
        else:
            print(0)
    else:
        if key[x] != key[y]:
            v = key[y]
            group[key[x]] += group[v]
            for i in group[v]:
                key[i] = key[x]
            group[v] = []

Submission status: Accepted

Solution code:
# AOJ DSL_1 A Set - Disjoint Set: Union Find Tree
# Python3 2017.6.23 bal4u

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

n, q = map(int, input().split())
u = UnionSet(n)
for i in range(q):
	cmd, x, y = map(int, input().split())
	if cmd == 0: u.unite(x, y)
	else: print(1 if u.connected(x, y) else 0)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.N = N
        self.parent = list(range(N))

    def root(self, x):
        path_to_root = []
        while self.parent[x] != x:
            path_to_root.append(x)
            x = self.parent[x]
        for node in path_to_root:
            self.parent[node] = x  # パス圧縮
        return x

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

    def unite(self, x, y):
        self.parent[self.root(x)] = self.root(y)

    def __str__(self):
        groups = {}
        for x in range(self.N):
            root = self.root(x)
            if root in groups.keys():
                groups[root].append(x)
            else:
                groups[root] = [x]
        result = ""
        for root in groups.keys():
            result += str(groups[root]) + "\n"
        return result

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

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().split())

arr = []

for i in range(n):
	arr.append(i)

def root(i):
	t = i
	while arr[t] != t:
		t = arr[t]

	return t

for i in range(m):
	query,x,y = map(int,raw_input().split())

	if query == 0:
		if root(y) == root(x):
			next 
		else :
			arr[root(y)] = root(x)

	else :
		print 1 if root(x) == root(y) else 0

Submission status: Accepted

Solution code:
def main():
    n,q = [int(i) for i in input().split()]
    #自分自身が親
    par = [ i for i in range(n)]
    #ランク
    rank = [ 0 for i in range(n)]
    #親を返す関数
    def find(x):
        if par[x] == x:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    #木を結合する
    def unite(x,y):
        x = find(x)
        y = find(y)
        if x == y:
            return
        if rank[x]<rank[y]:
            par[x] = y
            return
        elif rank[y]<rank[x]:
            par[y] = x
            return
        else:
            par[x] = y
            rank[y] +=1
            return

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.size   = n
        self.rank   = [0] * n
        self.weight = [1] * n
        self.parent = [i for i in range(n)]
        
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
            
    def same(self, x, y):
        return self.find(x) == self.find(y)
        
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
            self.weight[y] += self.weight[x]
        else:
            self.parent[y] = x
            self.weight[x] += self.weight[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] = self.rank[x] + 1
            
if __name__ == "__main__":
    n, q = map(int, raw_input().split())

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    n, q = (int(s) for s in stdin.readline().split())
    s = [{i} for i in range(n)]

    for _ in range(q):
        com, x, y = (int(s) for s in stdin.readline().split())
        if com:
            if x in s[x] and y in s[x]:
                print(1)
            else:
                print(0)
        else:
            a = s[x]
            b = s[y]
            if a is not b:
                a |= b
                for i in a:
                    s[i] = a


main()

Submission status: Accepted

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

if __name__ == "__main__":
    
    
    n, q = map(int, input().split())
    u = UnionFind(n)

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

        if com == 1:
            ans = u.same_check(x, y)
            ans_list.append(ans)
        else:
            u.union(x, y)

    for num in ans_list:
        print(int(num))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, x):
        r = x
        while self.parent[r] != r:
            r = self.parent[r]
        while self.parent[x] != r:
            x, self.parent[x] = self.parent[x], r
        return r

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

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

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

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

Submission status: Accepted

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

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy


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

for i in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        uni.merge(x, y)
    else:
        print(int(uni[x] == uni[y]))

Submission status: Accepted

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

buf = [i for i in range(n)]
height = [1] * n

def find(i):
    while i != buf[i]:
        i = buf[i]
    return i

def union(i, j):
    i = find(i)
    j = find(j)
    if height[i] >= height[j]:
        buf[j] = i
        height[i] = max(height[i], height[j] + 1)
    else:
        buf[i] = j
        height[j] = max(height[j], height[i] + 1)

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

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parent = [i for i in range(self.n)]
    self.rank = [0] * self.n
  
  def find_root(self, x):
    if self.parent[x] == x:
      return x
    else:
      self.parent[x] = self.find_root(self.parent[x])
      return self.parent[x]
  
  def unite(self, x, y):
    rx = self.find_root(x)
    ry = self.find_root(y)
    if rx == ry:
      return
    if self.rank[rx] < self.rank[ry]:
      self.parent[rx] = ry
    else:
      self.parent[ry] = rx
      if self.rank[rx] == self.rank[ry]:
        self.rank[rx] += 1
  
  def is_same(self, x, y):
    return self.find_root(x) == self.find_root(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.unite(a, b)
  else:
    if uf.is_same(a, b):
      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 union(self, x, y):
        '''
        xとyは-=1して使う
        '''
        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())
u = UnionFind(n)
ans_ls = []
for i in range(Q):
    q,x,y = map(int,input().split())
    if q == 1:
        if u.same(x,y):
            ans_ls.append(1)
        else:
            ans_ls.append(0)
    else:
        u.union(x,y)
for i in range(len(ans_ls)):
    print(ans_ls[i])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N))
        self._rank = [0] * self.N
        self._size = [1] * self.N

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

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

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

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

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


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 == 0:
            uf.union(x, y)
        else:
            ans.append(int(uf.same_set(x, y)))

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()