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:
class UnionFind:
    __slots__ = ["N", "root"]

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

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

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

        while self.root[x] >= 0:
            self.root[x], x = r, self.root[x]

        return r

    def union(self, x, y):
        """x, yが属する木をunion"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.root[y] < self.root[x]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

    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(i) == _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:
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = 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: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        r = a
        while self.parent_or_size[r] >= 0:
            r = self.parent_or_size[r]

        while self.parent_or_size[a] >= 0:
            self.parent_or_size[a], a = r, self.parent_or_size[a]

        return r

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        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 list(filter(lambda r: r, result))


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = DSU(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.merge(u, v)
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = 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: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        update_list = []
        while self.parent_or_size[a] >= 0:
            update_list.append(a)
            a = self.parent_or_size[a]

        for i in update_list:
            self.parent_or_size[i] = a

        return a

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        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 list(filter(lambda r: r, result))


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = DSU(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.merge(u, v)
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = 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: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        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: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        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 list(filter(lambda r: r, result))


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = DSU(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.merge(u, v)
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_dsu_code = """
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = 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: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        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: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        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 list(filter(lambda r: r, result))
"""

atcoder.dsu = types.ModuleType('atcoder.dsu')
exec(_atcoder_dsu_code, atcoder.dsu.__dict__)
DSU = atcoder.dsu.DSU

# https://atcoder.jp/contests/practice2/tasks/practice2_a

import sys

# from atcoder.dsu import DSU


def main() -> None:
    n, q = map(int, sys.stdin.readline().split())
    dsu = DSU(n)

    for _ in range(q):
        t, u, v = map(int, sys.stdin.readline().split())
        if t == 0:
            dsu.merge(u, v)
        if t == 1:
            if dsu.same(u, v):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = 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: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        while self.parent_or_size[a] >= 0:
            a = self.parent_or_size[a]

        return a

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        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 list(filter(lambda r: r, result))


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = DSU(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.merge(u, v)
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
from sys import stdin
readline = stdin.readline
def i_input(): return int(readline().rstrip())
def i_map(): return map(int, readline().rstrip().split())
def i_list(): return list(i_map())

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

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

    def unite(self, x, y) -> bool:
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1
        return True

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

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

    def is_same(self, x, y) -> bool:
        return self.root(x) == self.root(y)

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

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

def main():
    N, Q = i_map()
    U = UnionFind(N)
    for _ in range(Q):
        t, u, v = i_map()
        if t == 1:
            print(1 if U.is_same(u, v) else 0)
        else:
            U.unite(u, v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#https://qiita.com/white1107/items/52fd4149bb1846862e38

N, Q = map(int,input().split())
par = [i for i in range(N+1)]

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    
    
for i in range(Q):
    t, u, v = map(int,input().split())
    if t == 0:
        unite(u,v)
    else:
        if same(u,v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class Unionfind():
  def __init__(self,n=10**6):
    self.n=n
    self.root=[-1]*(n+1)
    self.rnk=[0]*(n+1)
  def find(self,x):
    if(self.root[x]<0):
      return x
    else:
      self.root[x]=self.find(self.root[x])
      return self.root[x]
  def unite(self,x,y):
    x=self.find(x)
    y=self.find(y)
    if(x==y):return
    elif(self.rnk[x] > self.rnk[y]):
      self.root[x]+=self.root[y]
      self.root[y]=x
    else:
      self.root[y]+=self.root[x]
      self.root[x]=y
      if(self.rnk[x]==self.rnk[y]):
        self.rnk[y]+=1
  def same(self,x,y):
    return self.find(x)==self.find(y)
  def count(self,x):
    return -self.root[self.find(x)]
uf=Unionfind()
n,q=map(int,input().split())
for _ in range(q):
  t,u,v=map(int,input().split())
  if t:print(int(uf.same(u,v)))
  else:uf.unite(u,v)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline


class UnionFind:
    # あり本実装
    # rankとrootの配列を1つで賄う方法
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n

    # 根を求める
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 同じかどうかの判定
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.find(x)

    # 　2つの集合の合体
    # 重みが大きい方に小さい方をつけるようにする
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False

        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True


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

UF = UnionFind(n)
for _ in range(q):
    t, u, v = map(int, input().split())
    if t:
        print(int(UF.is_same(u, v)))
    else:
        UF.unite(u, v)

Submission status: Accepted

Solution code:
import sys


def read():
    return sys.stdin.buffer.readline().rstrip()


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


def main():
    n, q = map(int, read().split())
    uf = UnionFind(n)
    for _ in range(q):
        t, u, v = map(int, read().split())
        if t == 0:
            uf.union(u, v)
        else:
            print(int(uf.same(u, v)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, n):
    self.par = [i for i in range(n+1)]
    self.rank = [0] * (n+1)
 
    # 検索
  def find(self, x):
    if self.par[x] == x:
      return x
    else:
      self.par[x] = self.find(self.par[x])
      return self.par[x]
 
  # 併合
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if self.rank[x] < self.rank[y]:
      self.par[x] = y
    else:
      self.par[y] = x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
 
  # 同じ集合に属するか判定
  def same_check(self, x, y):
    return self.find(x) == self.find(y)
n,q = map(int,input().split())
uf = UnionFind(n)
for _ in range(q):
  t,u,v = map(int,input().split())
  if t == 0:
    uf.union(u,v)
  else:
    print(int(uf.same_check(u,v)))

Submission status: Accepted

Solution code:
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = 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: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        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: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        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 list(filter(lambda r: r, result))
      
n,q=map(int,input().split())
dsu=DSU(n)
for i in range(q):
  t,u,v=map(int,input().split())
  if(t==0):
    dsu.merge(u,v)
  else:
    if(dsu.same(u,v)):
      print(1)
    else:
      print(0)

Submission status: Accepted

Solution code:
import typing

class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = 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: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        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: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        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 list(filter(lambda r: r, result))

N, Q = map(int, input().split())
dsu = DSU(N)

for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        # add line
        dsu.merge(u, v)
    else:
        # concat
        if dsu.same(u, v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [i for i in range(n)] # parents
        self.rank = [1] * n # height of tree
        self.size = [1] * n # size[i] -> iをrootとするgroupのサイズ

    # 木の根を返す
    def find(self, x):
        if self.parents[x] == x:
            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.rank[x] < self.rank[y]:
            self.parents[x] = y
            self.size[y] += self.size[x] 
        else:
            self.parents[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じグループに属しているかを判定する
    def same(self, x, y):
        return self.find(x) == self.find(y)

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

Submission status: Accepted

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

    def find(self, x: int) -> int:
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x: int, y: int) -> None:
        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: int) -> int:
        return -self.parents[self.find(x)]

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

    def members(self, x: int):
        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) -> int:
        return len(self.roots())

    def sizes(self):
        return {x: self.size(x) for x in self.roots()}

    def all_group_members(self):
        d = {}
        for i in range(self.n):
            p = self.find(i)
            d[p] = d.get(p, []) + [i]
        return d

    def __str__(self):
        return '\n'.join('{}: {}'.format(k, v) for k, v in self.all_group_members().items())


def resolve():
    n, q = map(int, input().split())
    u = UnionFind(n)
    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 0:
            u.union(a, b)
        else:
            if u.same(a, b):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    resolve()

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 sizes(self):
        return {x: self.size(x) for x in self.roots()}

    def all_group_members(self):
        d = {}
        for i in range(self.n):
            p = self.find(i)
            d[p] = d.get(p, []) + [i]
        return d

    def __str__(self):
        return '\n'.join('{}: {}'.format(k, v) for k, v in self.all_group_members().items())


def resolve():
    n, q = map(int, input().split())
    u = UnionFind(n)
    for _ in range(q):
        t, a, b = map(int, input().split())
        if t == 0:
            u.union(a, b)
        else:
            if u.same(a, b):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())

def unite(x,y):
	rx=root(x);ry=root(y)
	if rank[rx]>rank[ry]:
		parent[ry]=rx
		size[rx]+=size[ry]
	else:
		parent[rx]=ry
		size[ry]+=size[rx]
		if rank[rx]==rank[ry]:
			rank[ry]+=1
def root(x):
	if x!=parent[x]:
		return root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
parent=list(range(n))
rank=[0]*n
size=[1]*n

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

Submission status: Accepted

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

class DSU:
    __slots__ = ["_n", "parent_or_size"]
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        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):
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        while self.parent_or_size[a] >= 0:
            a = self.parent_or_size[a]
        return a

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

main()

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.readline
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,read().split())
UF=UnionFind(N)
for _ in range(Q):
    t,u,v=map(int,read().split())
    if t:
        print(int(UF.same(u,v)))
    else:
        UF.union(u,v)

Submission status: Accepted

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

class DSU:
    __slots__ = ["_n", "parent_or_size"]
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        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):
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        stack = []
        while self.parent_or_size[a] >= 0:
            stack.append(a)
            a = self.parent_or_size[a]
        for i in stack:
            self.parent_or_size[i] = a
        return a

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

main()

Submission status: Accepted

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

class DSU:
    __slots__ = ["_n", "parent_or_size"]
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        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):
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        stack = []
        while self.parent_or_size[a] >= 0:
            stack.append(a)
            a = self.parent_or_size[a]
        for i in stack:
            self.parent_or_size[i] = a
        return a

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

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