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:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')


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

parents = [i for i in range(n)]
size = [1 for _ in range(n)]


def find(x):
    if x != parents[x]:
        parents[x] = find(parents[x])
    return parents[x]


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


def unite(x, y):
    x_root = find(x)
    y_root = find(y)
    if x_root == y_root:
        return
    if x_root < y_root:
        x_root, y_root = y_root, x_root
    parents[y_root] = x_root
    size[x_root] += size[y_root]


for com, x, y in queries:
    if com == 0:
        unite(x, y)
    else:
        if 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):  # 要素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())


N, Q = map(int, input().split())
uf = UnionFind(N)
ans = []
for _ in range(Q):
    com, x, y = map(int, input().split())
    if com:
        if uf.same(x, y):
            ans.append(1)
        else:
            ans.append(0)
    else:
        uf.union(x, y)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
#setrecursionlimit(10**5)
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納
        # par[x]=xの時そのノードは根　
        self.par = [i for i in range(n + 1)]
        # rank
        self.rank = [0] * (n + 1)
        self.size = [1] * (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 check(self, x, y):
        # 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
        # rankの小さいものを大きいほうにくっつける
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def count_group(self):
        return len({self.find(x) for x in range(n)})

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:
        if uf.check(x, y):print(1)
        else:print(0)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

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

def main():
    n, q = map(int, readline().split())
    uf = UnionFind(n)
    for _ in range(q):
        com, x, y = map(int, readline().split())
        if com == 0:
            uf.union(x, y)
        else:
            px = uf.find(x)
            py = uf.find(y)
            print((px == py)*1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=ja
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class UnionFind:
    def __init__(self, n):
        # 初期状態は全要素が根なので、親は自分自身
        self.par = [i for i in range(n+1)]
        # 集団の要素数(size)を格納する(初期は全て1)
        self.size = [1] * (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])
  
    # 結合(unite)する関数
    def unite(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        # サイズを比較し、小さい方を大きい方に繋げる
        if self.size[x] < self.size[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
           
    # 同じグループに属するかを判定する関数
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    
    # 要素が属する木のサイズを返す関数
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # グループ数を返す関数
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c


def main():
    n,q,*query = map(int, read().split())

    uf = UnionFind(n)

    for com, x, y in zip(*[iter(query)]*3):
        if com:
            print(1 if uf.is_same(x, y) else 0)
        else:
            uf.unite(x, y)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


# import math
# import bisect

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize
# MOD = 10 ** 9 + 7

# ===CODE===
def main():
    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())
    que = UnionFind(n)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N, Q = map(int, input().split())
QE = [list(map(int, input().split())) for _ in range(Q)]

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*(n)
        self.size = [1]*(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_check(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:
            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
            self.size[x] += self.size[y]

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


uni = UnionFind(N)
for qe in QE:
    com, x, y = qe
    if com==0:
        uni.union(x, y)
    elif com==1:
        if uni.same_check(x, y):
            print(1)
        else:
            print(0)
    else:
        print('miss')

Submission status: Accepted

Solution code:
#A
#UnionFind
class UF:
    def __init__(self,n):
        self.n = n
        self.root = [-1]*n #root[x]<0 ならxが根かつその値が木の要素数
        self.rank = [0]*n #木の深さ
    def __del__(self):
        pass
        
    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
        
        if 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 same(self,x,y):
        return self.find(x) == self.find(y) #bool
    
    def count(self,x):
        return -self.root[self.find(x)]
    
N,Q = map(int,input().split())
uf = UF(N)

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

Submission status: Accepted

Solution code:
import sys

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


# main
n, q = map(int, sys.stdin.readline().strip().split())

uf = UnionFind(n)
for _ in range(q):
    query_type, x, y = map(int, sys.stdin.readline().strip().split())
    if query_type == 0:
        uf.union(x, y)
    elif query_type == 1:
        is_same = uf.same(x, y)
        print(1 if is_same else 0)

Submission status: Accepted

Solution code:
rank = []
p = []


def makeSet(x):
    p.append(x)
    rank.append(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 same(x, y):
    return findSet(x) == findSet(y)


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

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

Submission status: Accepted

Solution code:
#Union Find

class UnionFind:
    """
    par  : 木の親要素を管理par[x]==xのときそのノードは根,
            初期状態例:[0,1,2,3]それぞれが親
                        [0,0]のとき0が根で1の親は0であることを示す
    rank : 木の高さを格納,併合する際に木の高さが高いものに低いものをくっつける形になるから

    """
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0] * (n)
        #print(self.rank)

    """
    引数のノードの根を検索
    再起関数で親の親の親の...という形で根にたどり着くまで繰り返す
    """
    # 検索
    def findSet(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
        # 根でないなら、親の要素で再走査
            # 走査する過程で親を書き換える(根を親につなぎなおす)
            self.par[x] = self.findSet(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        #根を探す
        x = self.findSet(x)
        y = self.findSet(y)
        # 木の高さを比較し,高いほうに低いほうをくっつける
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
        # 木の高さが同じなら片方の木の高さを1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


    """
    同じ集合に属するか判定＝二つの要素の根が同じかどうか判定
    """
    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.findSet(x) == self.findSet(y)


def main():
    p = []  ##appendのために宣言が必要
    n, q = map(int, input().split())
    # n：整数の値の範囲（n-1）
    # q：実行されるクエリの数
    # 入力受付
    i = 0
    while i < q:
        try:
            p.append(list(map(int, input().split())))
            i = i + 1
        except:
            break;
    x = UnionFind(n)

    i = 0
    while i < len(p):
        if(p[i][0] == 0):
                x.union(p[i][1],p[i][2])
        if(p[i][0] == 1):
            result = x.same_check(p[i][1],p[i][2])
            if result == False:
                print(0)
            if result == True:
                print(1)

        i = i + 1







if __name__ == '__main__':
    main()

Submission status: Accepted

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

class UnionFind:
    N = 0
    cost = 0
    par = []
    
    def init(N):
        UnionFind.N = N
        UnionFind.par = [i for i in range(N)]

    def find(v):
        c = 0
        u = v
        while v != UnionFind.par[v]:
            v = UnionFind.par[v]
            c += 1

        if c > 10:
            while u != v: u, UnionFind.par[u] = UnionFind.par[u], v

        return v

    def union(v, u, c=0):
        vr = UnionFind.find(v)
        ur = UnionFind.find(u)

        if vr == ur: return True

        UnionFind.par[ur] = vr
        UnionFind.cost += c

        return False
            
    def get_cost():
        return UnionFind.cost

    def same(v, u):
        return UnionFind.find(v) == UnionFind.find(u)

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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] += 1

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

n,q = map(int, input().split())
p = [0]*n
rank = [0]*n

for x in range(n):
    makeSet(x)

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

Submission status: Accepted

Solution code:

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

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

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] = rank[y] + 1

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

def isSame(x, y):
    global p
    if(findSet(x) == findSet(y)):
        return True
    else:
        return False

if __name__ == "__main__":
    N, Q = (int(z) for z in input().split())
    p = [None] * N
    rank = [None] * N

    for i in range(N):
        makeSet(i)

    for i in range(Q):
        com_i, x, y = (int(z) for z in input().split())
        if(com_i == 0):
            #print("union")
            union(x, y)
        if(com_i == 1):
            #print("isSame")
            if(isSame(x, y) == False):
                print("0")
            else:
                print("1")

Submission status: Accepted

Solution code:
class Disjointset:

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

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

    def unite(self,x,y): return 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 findSet(self,x):
        if x != self.p[x]: self.p[x] = self.findSet(self.p[x])
        return self.p[x]

n,q = map(int,input().split())
ds = Disjointset(n)
ans = []
for _ in range(q): 
    com,x,y = map(int,input().split())
    if com == 0: ds.unite(x,y)
    else: ans.append("1" if ds.same(x,y) else "0")
print("\n".join(ans))

Submission status: Accepted

Solution code:
maxn = 100000

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

par = [0] * n
rank = [0] * n

#初期化
for i in range(n):
    par[i] = i
    rank[i] = 0

#判定(一番上野根を求める)
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
    
#結合
def unite(x , y):
    rx = find(x)
    ry = find(y)
    
    if rx == ry:
        return
    
    if rank[rx] < rank[ry]:
        par[rx] = ry
    elif rank[rx] > rank[ry]:
        par[ry] = rx
    else:
        par[ry] = x
        rank[rx] += 1      

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

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

Submission status: Accepted

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

    def print_set(self):
        print(self.parent)
        print(self.rank)

    def find_set(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find_set(self.parent[x])
        
        return self.parent[x]
    
    def unite(self, x, y):
        x_parent = self.find_set(x)
        y_parent = self.find_set(y)

        if self.rank[x_parent] > self.rank[y_parent]:
            self.parent[y_parent] = x_parent
        else:
            self.parent[x_parent] = y_parent
            if self.rank[x_parent] == self.rank[y_parent]:
                self.rank[y_parent] += 1

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

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

Submission status: Accepted

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

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

    def size(self, a):
        return -self.parent[self.root(a)]

    def connect(self, a, b) -> bool:
        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]

        self.parent[b] = a

        return True


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

Submission status: Accepted

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

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

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

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

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

    # 要素xが属するグループに属する要素をリストで返す
    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()}

    # print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    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 i 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:
n, q = map(int, input().split())
p = [-1]*n

def root(x):
    if p[x]==-1:
        return x
    
    p[x] = root(p[x])
    return p[x]

def unite(a, b):
    if root(a)!=root(b):
        if a>b:
            a,b = b,a
        p[root(b)] = root(a)
        
def same(a, b):
    if root(a)==root(b):
        return True
    else:
        return False
    
for i in range(q):
    c, a, b = map(int, input().split())
    if c==0:
        unite(a, b)
       # print(p)
    if c==1:
        if same(a, b):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
#=============================================================================
# DSL1_A
#=============================================================================
n,q=map(int,input().split())
parents=[i for i in range(n)]
deepth=[0 for _ in range(n)]

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

def unite(x,y):
    px=find(x)
    py=find(y)
    if deepth[px]>deepth[py]:
        parents[py]=px
        deepth[px]=max(deepth[px],deepth[py]+1)
    else:
        parents[px]=py
        deepth[py]=max(deepth[py],deepth[px]+1)

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

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

Submission status: Accepted

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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return False
        if x > y:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

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

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



def main():
    n, _, *A = map(int, open(0).read().split())
    uf = UnionFind(n)

    for a, x, y in zip(*[iter(A)]*3):
        if a == 0:
            uf.unite(x, y)
        else:
            print(1 if uf.same(x, y) else 0)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

u = UnionFind(n)
for i in range(q):
	c, x, y = map(int, input().split())
	if c==0:
		u.union(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.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:
            if self.parents[x]>self.parents[y]:
                x,y=y,x

            self.parents[x]+=self.parents[y]
            self.parents[y]=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)
    elif com==1:
        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.p = [i for i in range(n)]
        self.rank = [0]*n

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

class DisjointSet(object):
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0]*n

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

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

    def link(self, x, y):
        if self.rank[x] > self.rank[y]:
            self.p[y] = x
        else:
            self.p[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
    
    def find_set(self, x):
        if x != self.p[x]:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]


if __name__ == '__main__':
    n, q = map(int, input().split())

    ds = DisjointSet(n)

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

Submission status: Accepted

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

par = [-1]*(n+1)

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

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

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

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