Problem:


Score : 100 points

Problem Statement

You are given an undirected graph with N vertices and 0 edges. Process Q queries of the following types.

0 u v: Add an edge (u, v).

1 u v: Print 1 if u and v are in the same connected component, 0 otherwise.

Constraints

1 \leq N \leq 200,000

1 \leq Q \leq 200,000

0 \leq u_i, v_i \lt N

Input

Input is given from Standard Input in the following format:

N Q
t_1 u_1 v_1
t_2 u_2 v_2
:
t_Q u_Q v_Q

出力

For each query of the latter type, print the answer.

Sample Input 1

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

Sample Output 1

0
1
0
1



Sample input:
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3


Sample output:
0
1
0
1

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, n):
        self._parent = [i for i in range(n)]
        self._rank = [0 for _ in range(n)]
        self._group_size = [1 for _ in range(n)]
        self.num_of_groups = n

    def find(self, x):
        # vs = []
        while self._parent[x] != x:
            # vs.append(x)
            x = self._parent[x]
        # for v in vs: self._parent[v] = x
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self._rank[px] < self._rank[py]:
            self._parent[px] = py
            self._group_size[py] += self._group_size[px]
        else:
            self._parent[py] = px
            self._group_size[px] += self._group_size[py]
        if self._rank[px] == self._rank[py]:
            self._rank[py] += 1
        self.num_of_groups -= 1

    def is_same(self, x, y): return self.find(x) == self.find(y)
    def group_size(self, x): return self._group_size[self.find(x)]


def main():
    N, Q = LI()
    TUV = LIR(Q)

    uf = UnionFind(N+1)

    for t, u, v in TUV:
        if t == 0:
            uf.union(u, v)
        else:
            print(int(uf.is_same(u, v)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, n):
        self._parent = [i for i in range(n)]
        self._rank = [0 for _ in range(n)]
        self._group_size = [1 for _ in range(n)]
        self.num_of_groups = n

    def find(self, x):
        vs = []
        while self._parent[x] != x:
            vs.append(x)
            x = self._parent[x]
        for v in vs: self._parent[v] = x
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self._rank[px] < self._rank[py]:
            self._parent[px] = py
            self._group_size[py] += self._group_size[px]
        else:
            self._parent[py] = px
            self._group_size[px] += self._group_size[py]
        if self._rank[px] == self._rank[py]:
            self._rank[py] += 1
        self.num_of_groups -= 1

    def is_same(self, x, y): return self.find(x) == self.find(y)
    def group_size(self, x): return self._group_size[self.find(x)]


def main():
    N, Q = LI()
    TUV = LIR(Q)

    uf = UnionFind(N+1)

    for t, u, v in TUV:
        if t == 0:
            uf.union(u, v)
        else:
            print(int(uf.is_same(u, v)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if len(args) > 0 else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, n):
        self._parent = [i for i in range(n)]
        self._rank = [0 for _ in range(n)]
        self._group_size = [1 for _ in range(n)]
        self.num_of_groups = n

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self._rank[px] < self._rank[py]:
            self._parent[px] = py
            self._group_size[py] += self._group_size[px]
        else:
            self._parent[py] = px
            self._group_size[px] += self._group_size[py]
        if self._rank[px] == self._rank[py]:
            self._rank[py] += 1
        self.num_of_groups -= 1

    def is_same(self, x, y): return self.find(x) == self.find(y)
    def group_size(self, x): return self._group_size[self.find(x)]


def main():
    N, Q = LI()
    TUV = LIR(Q)

    uf = UnionFind(N+1)

    for t, u, v in TUV:
        if t == 0:
            uf.union(u, v)
        else:
            print(int(uf.is_same(u, v)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
parents=[i for i in range(n)]
rank=[i for i in range(n)]
def find(a):
    if parents[a]!=a:
        return find(parents[a])
    return a
        

def union(a,b):
    xa=find(a)
    xb=find(b)
    if xa==xb:
        return
    if rank[xa]>rank[xb]:
        parents[xb]=xa
        
    elif rank[xa]<rank[xb]:
        parents[xa]=xb
    else:
        parents[xa]=xb
        rank[xb]+=1

for i in range(m):
    h,a,b=list(map(int,input().split()))
    if h==0:
        union(a,b)
    else:
        x=find(a)
        y=find(b)
        
        print(1 if x==y else 0)

Submission status: Accepted

Solution code:
n,q=map(int, input().split())
*p,=range(n+1)
r=[0]*(n+1)
def par(x):
    if p[x]==x:
        return x
    res = p[x]=par(p[x])
    return res

def union(x,y):
    px=par(x);py=par(y)
    if px==py:
        return
    if r[px]>r[py]:
        p[py]=px
        r[py]+=1
    elif r[px]<r[py]:
        p[px]=py
        r[px]+=1
    else:
        p[px]=py
        r[py]+=1
for _ in range(q):
    t,u,v=map(int, input().split())
    if t:
        print(1 if par(u)==par(v) else 0)
    else:
        union(u,v)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

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

def init(n):
    for i in range(n):
        par[i] = i 
        rank[i] = 0 

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

    # ここをしっかり理解する
    else:
        par[x] = root(par[x])
        return par[x]

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

def unite(x, y): 
    x = root(x)
    y = root(y)
    if x == y:
        return
    par[x] = y 

# main
t = [0 for _ in range(q)]
u = [0 for _ in range(q)]
v = [0 for _ in range(q)]

init(n)
for i in range(q):
    t[i], u[i], v[i] = map(int, input().split())
    if t[i] == 0:unite(u[i], v[i])
    else:print(int(same(u[i], v[i])))

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["N", "root", "rank"]

    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        rank:ランク
        """
        self.N = N
        self.root = [-1] * N
        self.rank = [0] * N

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

    def find(self, x):
        """頂点xの根を見つける"""
        while self.root[x] >= 0:
            x = self.root[x]
        return x

    def union(self, x, y):
        """x,yが属する木をunion"""
        # 根を比較する
        # すでに同じ木に属していた場合は何もしない.
        # 違う木に属していた場合はrankを見てくっつける方を決める.
        # rankが同じ時はrankを1増やす
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) 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()}


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = UnionFind(n)
res = []
for i in range(q):
    t, u, v = map(int, input().split())
    if t:
        res.append(int(uf.same(u, v)))
    else:
        uf.union(u, v)
print(*res,sep="\n")

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["N", "root", "rank"]

    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        rank:ランク
        """
        self.N = N
        self.root = [-1] * N
        self.rank = [0] * N

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

    def find(self, x):
        """頂点xの根を見つける"""
        while self.root[x] >= 0:
            x = self.root[x]
        return x

    def union(self, x, y):
        """x,yが属する木をunion"""
        # 根を比較する
        # すでに同じ木に属していた場合は何もしない.
        # 違う木に属していた場合はrankを見てくっつける方を決める.
        # rankが同じ時はrankを1増やす
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

    def same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) 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()}


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = UnionFind(n)
res = []
for i in range(q):
    t, u, v = map(int, input().split())
    if t:
        res.append(int(uf.same(u, v)))
    else:
        uf.union(u, v)
print("\n".join(map(str, res)))

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):
  A=list(map(int,input().split()))
  if A[0]==0:
    uf.union(A[1],A[2])
  else:
    if uf.same(A[1],A[2]):
      print(1)
    else:
      print(0)

Submission status: Accepted

Solution code:
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c${@o!EW0y47~@)KM*bkB#mP=*bap;U;7hXFenmZ3y~#3lACp3KUz{#x5ad^$@lm~KJgBu3UP``hZZz9{lt6h#BR4<-7O(ygq|e+mdc0jnGJSCCaj4VA~%sW+6u0jRww3O<6zDA=8**zaqqaekYr$H8r>_^cw|Ma24-DkJPIq(??cqb`BsqxS~%Is$RGw3m+pz{fJ^Y|x#NCjykTc=N1z6Tb0E~{tdAsN^#`PRK@qLL5puX*35jRGKM}owM6W)#_V&+Yn3}=43Jf1H(0B+{!6;{YrQ7ui=p;?LQ)nInP+7^(hoX%#5zO{IH^(FT9uvarlsGL2^E43X*8dUaSR<!SGUF2z)L;ApWCxzhhtT5@dNS69&9+#VJ#WZwt~KhLdCt?mES+ycl*-=l9-|nzuZc*y=i>6*fKX<${c2X4rv?EXJmmCsP#WQ|aPCB45#B84I}`E~emv6Nc;uINWL6V!4~GZX5ob@F40?<cJ-1l&rOH1&58O*CG<Z#Kl^UM?pxseKEwkr*ohRuI+tMdBlYq8NzNx;+U#6--HtG3FRTeEnAT4oAguDSC80*zPdcGcc")))
    os.system('cythonize -i -3 -b solve.pyx')
import solve

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):
    t,u,v = map(int,input().split())
    if t == 0:
        uf.union(u,v)
    else:
        print(uf.same(u,v)*1)

Submission status: Accepted

Solution code:
code = """
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
cdef extern from "/opt/atcoder-stl/atcoder/dsu.hpp" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
cdef class DSU:
    cdef dsu *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new dsu(n)
    cpdef int merge(self, int a, int b):
        return self._thisptr.merge(a, b)
    cpdef bool same(self, int a, int b):
        return self._thisptr.same(a, b)
    cpdef int leader(self, int a):
        return self._thisptr.leader(a)
    cpdef int size(self, int a):
        return self._thisptr.size(a)
"""
import os,sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

# ↑ここまでライブラリ↓ここから解法

import sys
import atcoder
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
dsu = atcoder.DSU(n)
res = []
for i in range(q):
    t, u, v = map(int, input().split())
    if t:
        if dsu.same(u, v): res.append(1)
        else: res.append(0)
    else:
        dsu.merge(u, v)
print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
tuv=[]
for i in range(q):
  tuv.append(input())

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())
 
uf = UnionFind(n)

for i in range(q):
  t,u,v=tuv[i].split(" ")
  u=int(u)
  v=int(v)
  if t=="0":
    uf.union(u,v)
  else:
    if uf.same(u,v):
      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:
            st = []
            while self.parents[x] >= 0:
                st.append(x)
                x = self.parents[x]
            for y in st:
                self.parents[y] = x
            return 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)

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

N,Q = map(int,input().split())
uf = UnionFind(N)
for i in range(Q):
    t,u,v = map(int,input().split())
    if t:
        print(int(uf.same(u,v)))
    else:
        uf.union(u,v)

Submission status: Accepted

Solution code:
class DSU():
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n
    
    def merge(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), self.leader(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    
    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]
    
    def groups(self):
        leader_buf = [self.leader(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[leader_buf[i]].append(i)
        return [r for r in result if r != []]


def main():
   n, q = map(int, input().split()) 
   d = DSU(n)
   for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
           d.merge(u, v)
        else:
            print(1 if d.same(u, v) else 0) 

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# by size
# 0-indexed
class UnionFind:
  N=0
  parent=None
  size=None
  def __init__(self,N):
    self.N=N
    self.parent=[i for i in range(self.N)]
    self.size=[1]*self.N
    
  def root(self,x):
    while x!=self.parent[x]:
      self.parent[x]=self.parent[self.parent[x]]
      x=self.parent[x]
    return 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:
      return
    if self.size[x]>self.size[y]:
      # 大きい方にくっつける
      self.parent[y]=x
      self.size[x]+=self.size[y]
    else:
      self.parent[x]=y
      self.size[y]+=self.size[x]
      
  def get_group_size(self,x):
    return self.size[self.root(x)]
  
  def get_roots(self):
    r=set()
    for i in range(self.N):
      r.add(self.root(i))
    return r
  
  def show_parent(self):
    print(self.parent)
    
  def show_size(self):
    print(self.size)
    
import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())
UF = UnionFind(N)
for i in range(Q):
  t,u,v = map(int,readline().split())
  u -= 1
  v -= 1
  if t == 0:
    UF.unite(u,v)
  else:
    print(int(UF.same(u,v)))

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)

    def ans(self):
        print(len(set(self.par))-1)

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

for i in range(m):
    a,u,v=map(int,input().split())
    if a==0:
        uf.union(u,v)
    else:
        if uf.same_check(u,v):
            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 = 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):	#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)
ans = []
l = 0
for i in range(q):
    t,u1,u2 = map(int,input().split())
    if(t == 0):
        uf.union(u1,u2)
    else:
        if(uf.same(u1,u2)):
            ans.append(1)
        else:
            ans.append(0)
        l += 1

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

Submission status: Accepted

Solution code:
# unionfind:連結成分が欲しい場合などに使用
import sys
sys.setrecursionlimit(10**9)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]
def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x
    siz_list[par_x]+= siz_list[par_y]
def is_same(x,y):
  return get_par(x) == get_par(y)

N,Q=map(int,input().split())
par_list = list(range(N+1))
siz_list = [1]*(N+1)

for _ in range(Q):
  t,u,v=map(int,input().split())
  if t==0:
    merge(u,v)
  else:
    if is_same(u,v):
      print(1)
    else:
      print(0)

Submission status: Accepted

Solution code:
class dsu:
    def __init__(self, N):
        self.root = [-1 for _ in range(N)]
        self.size = [1 for _ in range(N)]

    def merge(self, x, y):
        x = self.leader(x)
        y = self.leader(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.root[x] = y
            self.size[y] += self.size[x]
        else:
            self.root[y] = x
            self.size[x] += self.size[y]
    
    def leader(self, x):
        while self.root[x] >= 0:
            x = self.root[x]
        return x

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

N, Q = [int(_) for _ in input().split()]
uf = dsu(N)

for i in range(Q):
    t, u, v = [int(_) for _ in input().split()]
    if t == 0:
        uf.merge(u, v)
    else:
        if uf.same(u, v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.vector cimport vector
cdef extern from "/opt/atcoder-stl/atcoder/dsu.hpp" namespace "atcoder":
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    def merge(self,a,b): return self.ptr.merge(a,b)
    def same(self,a,b): return self.ptr.same(a,b)
    def leader(self,a): return self.ptr.leader(a)
    def size(self,a): return self.ptr.size(a)
    def groups(self): return self.ptr.groups()
"""
import os
try:
    from dsu import *
except:
    open('dsu.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b dsu.pyx')

N,Q=map(int,input().split())
TUV=[list(map(int,input().split())) for i in range(Q)]
d=dsu_(N)
for t,u,v in TUV:
    if t==0:
        d.merge(u,v)
    else:
        print(1 if d.same(u,v) else 0)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

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

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

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

def main():
	N, Q = getlist()
	UF = UnionFind(N)
	for i in range(Q):
		q, u, v = getlist()
		if q == 0:
			UF.union(u, v)
		else:
			if UF.same_check(u, v):
				print(1)
			else:
				print(0)

if __name__ == '__main__':
	main()