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 root(x):
    path_to_root = []
    while P[x] != x:
        path_to_root.append(x)
        x = P[x]
    for node in path_to_root:
        P[node] = x # パス圧縮
    return x
def is_same_set(x,y):
    return root(x) == root(y)
def unite(x,y):
    P[root(x)] = root(y)

n,q = map(int,input().split())
P = [i for i in range(n)]
for _ in range(q):
    a,b,c = map(int,input().split())
    if a==0:
        unite(b,c)
    elif a==1:
        if is_same_set(b,c):
            print(1)
        else:
            print(0)

Submission status: Accepted

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

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

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


G = UnionFind(n)

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

    if com == 0:
        G.union(x, y)
    else:
        print(int(G.same(x, y)))

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self,size):
        self.rank=[0]*size
        self.p=[0]*size
        for i in range(size):
            self.makeSet(i)
    
    def makeSet(self,i):
        self.p[i]=i
        self.rank[i]=0
    
    def same(self,x,y):
        return self.findSet(x) == self.findSet(y)
    
    def unite(self, x,y):
        self.link(self.findSet(x), self.findSet(y))
    
    def link(self, x, y):
        if(self.rank[x] > self.rank[y]):
            self.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]

def main():
    n,q=list(map(int,input().split()))
    disjointSet = DisjointSet(n)
    for _ in range(q):
        cmds=list(input().split())
        if cmds[0] == '0':
            x,y=list(map(int,cmds[1:]))
            disjointSet.unite(x,y)
        elif cmds[0]=='1':
            x,y=list(map(int,cmds[1:]))
            if disjointSet.same(x,y) == True:
                print(1)
            else:
                print(0)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")

import sys,collections,math
sys.setrecursionlimit(1000000)

INF = float("inf")

N,Q = map(int,sys.stdin.readline().split())
COM = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) # multi line with multi param

parents = list(range(N))
def find(x):
  while parents[x] != x:
    x = parents[x]
    parents[x] = parents[parents[x]]
  return x
def union(s,t):
  sp = find(s)
  tp = find(t)
  if sp == tp:
    pass
  elif sp < tp:
    parents[sp] = tp
  else:
    parents[tp] = sp

for com,x,y in COM:
    if com == 0:
        union(x,y)
    else:
        if find(x) == find(y):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
com, x, y = [0] * q, [0] * q, [0] * q
for i in range(q):
    com[i], x[i], y[i] = map(int, input().split())

#初期化 par:親の番号 rank:高さ
par = [i for i in range(n)]
rank = [0 for _ in range(n)]
#木の根を求める
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x] 
#xとyが同じ集合に属するか否か
def same(x, y):
    return root(x) == root(y)
#xとyの属する集合を併合
def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
    if rank[x] == rank[y]:
        rank[x] += 1

#クエリ
for i in range(q):
    if com[i] == 0:
        unite(x[i], y[i])
    else:
        if same(x[i], y[i]):
            print(1)
        else:
            print(0)

Submission status: Accepted

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

class UnionFind():                                              # クラス　＝　インスタンスを返す関数（型とは違う? 、dictを例に説明？）
    def __init__(self, n):                                      # コンストラクタ　＝　インスタンスをどのように生成するか、どのような構造を持たせるかを定義
                                                                # 具体的にはオブジェクトにインスタンス変数を割り当てる事で、複雑な構造を持たせる役割を持つ
                                                                # ここでは 0 ~ n-1 までの整数にインスタンス変数parentsを割り当てる事で、
                                                                # 単なる整数から親子関係という内部構造を持つインスタンスを生成した。

        self.n = n                                              # インスタンスselfのインスタンス変数 n の値を定義
        self.parents = [-1] * n                                 # インスタンスselfのインスタンス変数 parents の値を定義


# 以下でインスタンスに作用する関数を定義。全ての関数はインスタンスを入力値としてインスタンス変数に基づいて処理される。

    def find(self, x):                                          # 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):                                      # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)                                        # xをxの根に置き換える
        y = self.find(y)                                        # yをyの根に置き換える

        if x == y:                                              # 根が同じなら置き換える必要なし
            return

        if self.parents[x] > self.parents[y]:                   # 子がたくさんある方を x とする
            x, y = y, x

        self.parents[x] += self.parents[y]                      # xの子の数を更新
        self.parents[y] = x                                     # yの親を更新

    def same(self, x, y):                                       # xとyが同じ根の子かを判定
        return self.find(x) == self.find(y)

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

A = UnionFind(n)

for c,x,y in [list(map(int,input().split())) for _ in range(q)]:
    if not c:
        A.union(x,y)
    else:
        print(int(A.same(x,y)))

Submission status: Accepted

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

# union find
# 最初は全て値であるとして初期化する parents[i] = i

# root(x) => xの根を返す関数
# unit(x,y) => root(x)とroot(y)が同じであればそのまま。違う場合は、xの根であるroot(x)をyの根であるroot(y)につける. 根が同じでない二つの木を合併する。
# same(x,y) => 二つのデータx,yが属する木が同じ場合、trueを返す。if root(x) == root(y)するだけ

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


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


def unit(x, y):
    root_x = root(x)
    root_y = root(y)
    if root_x < root_y:
        parents[root_y] = root_x
    else:
        parents[root_x] = root_y


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


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

Submission status: Accepted

Solution code:
from collections import deque


class UnionFind:
    def __init__(self, v):
        self.v = v
        self._tree = list(range(v + 1))

    def _root(self, a):
        queue = deque()
        while self._tree[a] != a:
            queue.append(a)
            a = self._tree[a]
        while queue:
            index = queue.popleft()
            self._tree[index] = a
        return a

    def union(self, a, b):
        root_a = self._root(a)
        root_b = self._root(b)
        self._tree[root_b] = root_a

    def find(self, a, b):
        return self._root(a) == self._root(b)


N, Q = map(int, input().split(' '))
queries = [tuple(map(int, input().split(' '))) for _ in range(Q)]
union_find = UnionFind(N - 1)
for p, a, b in queries:
    if p == 0:
        union_find.union(a, b)
    else:
        if union_find.find(a, b):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:

def search_root(x):
    i = x
    while True:
        if i == nodes[i]:
            nodes[x] = i
            return i
        else:
            i = nodes[i]

def unite(x,y):
    nodes[search_root(x)] = search_root(y)

def same(x,y):
    if search_root(x) == search_root(y):
        print(1)
    else:
        print(0)


n, q = map(int, input().split())
nodes = [i for i in range(n)]
commands = []
for _ in range(q):
    commands.append(input())
for cmd in commands:
    c,x,y = map(int,cmd.split())
    if c == 0:
        unite(x,y)
    else:
        same(x,y)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=ja
# union-find
# https://note.nkmk.me/python-union-find/


class UnionFind:
    def __init__(self, n):
        self.n = n
        # 各要素の親要素の番号を格納するリスト
        # 根がルートの時は、グループの要素数を格納　最初は全て根で要素数1
        self.parents = [-1] * n

    # 再帰 groupの根を返す
    # 経路圧縮あり
    def find(self, x):
        # 0より小さい場合は根
        if self.parents[x] < 0:
            # indexを返す
            return x
        else:
            # 根になるまで親を辿る
            # 経路圧縮 根のindexが全ての親に再帰的につく
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # groupを併合
    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
        # 根のグループ数を追加 xの方グループの要素数が多い前提なので多い方に寄せる
        self.parents[x] += self.parents[y]
        # 親(根)のindexを入れる
        self.parents[y] = x

    # xのgroupのサイズ
    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())

    # {root: [要素]}
    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())

uft = UnionFind(n)

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.par=[i for i in range(N)]
        self.siz=[1 for _ in range(N)]
        self.rank=[0 for _ in range(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,a,b):
        a=self.find(a)
        b=self.find(b)
        if a==b:
            return 0
        else:
            if self.rank[a]>self.rank[b]:
                self.par[b]=a
                self.siz[a]+=self.siz[b]
            else:
                self.par[a]=b
                self.siz[b]+=self.siz[a]
                if self.rank[a]==self.rank[b]:
                    self.rank[b]+=1
    def size(self,a):
        return self.siz[self.find(a)]
    def same(self,a,b):
        return self.find(a)==self.find(b)

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

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
# initialize
par = [-1] * n
rank = [0] * n

# Union Find Tree
def find(x):
    """ 根ノードの値を見つけて返す """
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x, y):
    """xとyを結合する"""
    rootx = find(x)
    rooty = find(y)

    if rootx == rooty:
        return False
    else:
        if rank[rootx] < rank[rooty]:
            par[rootx] = rooty
        else:
            par[rooty] = rootx
            if rank[rootx] == rank[rooty]: rank[rootx] += 1
        return True

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


for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        unite(x, y)
    elif com == 1:
        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 = self.find(x)  #x,yの木の根
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x  #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 == 0:
        uf.union(x,y)
    else:
        judge = uf.same(x,y)
        if judge:
            ans.append(1)
        else:
            ans.append(0)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group_count = 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

        self.group_count -= 1

        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 all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

Submission status: Accepted

Solution code:
class unionfind:
    sz = 0
    par = []
    def __init__(self, n):
        self.sz = n
        for i in range(n):
            self.par.append(-1)

    def find(self, a):
        if self.par[a]<0: return a
        self.par[a] = self.find(self.par[a])
        return self.par[a]
    
    def size(self, a):
        a = self.find(a)
        return -self.par[a]
    
    def same(self, a,b):
        return self.find(a) == self.find(b)

    def unite(self, a,b):
        a = self.find(a)
        b = self.find(b)
        if self.same(a,b): return False
        if self.size(a) < self.size(b):
            a,b=b,a
        self.par[a] += self.par[b]
        self.par[b] = a
        return True

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

def resolve():
    n, q = LI()
    uf = UnionFind(n)
    for _ in range(q):
        comxy = LI()

        com = comxy[0]
        x = comxy[1]
        y = comxy[2]

        if com==0:
            uf.unite(x, y)
        else:
            print(int(uf.same(x, y)))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
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 unite(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
            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 same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False 


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)
    if com == 1:
        print(int(UF.same(x, y)))

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

    def nums(self,x):
        return abs(self.parents[self.find(x)])

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

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

    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)
    if com==1:
        print(int(uf.same(x,y)))

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
commands = [0]*q
args = [[0,0] for _ in range(q)]
for i in range(q):
    tmp = list(map(int,input().split()))
    commands[i] = tmp[0]
    args[i] = tmp[1:3]

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 in range(self.n) if self.parents[i] < 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())

tree = UnionFind(n)

for i in range(q):
    if commands[i] == 0:
        tree.union(args[i][0],args[i][1])
    else:
        if tree.same(args[i][0],args[i][1]):
            print(1)
        else:
            print(0)

Submission status: Accepted

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

    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[y] < self.rank[x]:
            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]

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

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/1/DSL_1_A


class UnionFind:

    def __init__(self, size: int):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.size = size
        self.parent = [-1] * size

    def find(self, x: int) -> int:
        """
        xを含む集合の代表を求める
        """
        if self.parent[x] < 0:
            return x
        # 集合の代表にリンクを繋ぎ変える
        same_group_items = []
        while self.parent[x] >= 0:
            same_group_items.append(x)
            x = self.parent[x]
        for child in same_group_items:
            self.parent[child] = x
        return x

    def unite(self, x: int, y: int):
        """
        xを含む集合とyを含む集合を併合する
        """
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.parent[root_x] >= self.parent[root_y]:
                self.parent[root_x] += self.parent[root_y]
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] += self.parent[root_x]
                self.parent[root_x] = root_y

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


def solve():
    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)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

    def Unite(self,x,y):
        x=self.Find_Root(x)
        y=self.Find_Root(y)

        if x==y:return
        elif self.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 isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

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

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

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

    def group_members(self):
        return {i:self.members(i) for i in self.roots()}

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


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

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self, n):
    # 初期状態は親は自分自身
    self.parents = list(range(n))
  
  def find(self,x):
    if self.parents[x] == x:
      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:
      self.parents[y] = x

import sys
input = sys.stdin.readline
n, q = map(int,input().split())
uf = UnionFind(n)

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0]*n
    def find(self, x):
        if x == self.par[x]:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def check(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
    def union(self, x, y):
        parx = self.find(x)
        pary = self.find(y)
        if self.rank[parx] < self.rank[pary]:
            self.par[parx] = pary
        else:
            self.par[pary] = parx
            if self.rank[pary] == self.rank[parx]:
                self.rank[parx] += 1
n,q = map(int, input().split())
G = UnionFind(n)
ans = []
for _ in range(q):
    c,x,y = map(int, input().split())
    if c == 0:
        G.union(x,y)
    elif c == 1:
        if G.check(x,y) == True:
            ans.append(1)
        else:
            ans.append(0)
    # print(G.par,G.rank)
    # if c == 1:
    #     print(G.find(x),G.find(y),G.check(x,y))

for i in range(len(ans)):
    print(ans[i])