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:
from typing import List


class DSU:
    def __init__(self, n: int) -> None:
        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, 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: 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
        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 size(self, a: int) -> int:
        assert 0 <= a <= self._n
        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> List[List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]
        group_size = [0] * self._n
        for i in leader_buf:
            group_size[i] += 1
        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)
        result = [i for i in result if i]
        return result


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)

Submission status: Accepted

Solution code:
from typing import List


class DSU:
    def __init__(self, n: int) -> None:
        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, 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: 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
        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) -> List[List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]
        group_size = [0] * self._n
        for i in leader_buf:
            group_size[i] += 1
        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)
        result = [i for i in result if i]
        return result


import sys
input = sys.stdin.readline
n, q = map(int, input().split())
uf = DSU(n)
for i in range(q):
    t, u, v = map(int, input().split())
    if t:
        print(int(uf.same(u, v)))
    else:
        uf.merge(u, v)

Submission status: Accepted

Solution code:
from typing import List


class DSU:
    def __init__(self, n: int) -> None:
        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, 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: 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
        result = self.leader(self.parent_or_size[a])
        self.parent_or_size[a] = result
        return result

    def size(self, a: int) -> int:
        assert 0 <= a <= self._n
        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> List[List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]
        group_size = [0] * self._n
        for i in leader_buf:
            group_size[i] += 1
        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)
        result = [i for i in result if i]
        return result


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)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

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 = [int(x) for x in input().split()]

    uf = UnionFind(N)

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




if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve():
    N, q = map(int, input().split())
    root = [-1] * N

    def find(x: int) -> int:
        if root[x] < 0:
            return x
        else:
            while root[x] >= 0:
                x = root[x]
            return x

    def union(x: int, y: int):
        x = find(x)
        y = find(y)
        if x == y:
            return
        if root[x] > root[y]:
            x, y = y, x
        root[x] += root[y]
        root[y] = x

    for _ in range(q):
        t, u, v = map(int, input().split())
        if t:
            print(int(find(u) == find(v)))
        else:
            union(u, v)


solve()

Submission status: Accepted

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


def solve():
    N, q = map(int, input().split())
    root = [-1] * N
    rank = [0] * N

    def find(x: int) -> int:
        if root[x] < 0:
            return x
        else:
            while root[x] >= 0:
                x = root[x]
            return x

    def union(x: int, y: int):
        x = find(x)
        y = find(y)
        if x == y:
            return
        elif rank[x] > rank[y]:
            root[x] += root[y]
            root[y] = x
        else:
            root[y] += root[x]
            root[x] = y
            if rank[x] == rank[y]:
                rank[y] += 1

    for _ in range(q):
        t, u, v = map(int, input().split())
        if t:
            print(int(find(u) == find(v)))
        else:
            union(u, v)


solve()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i 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 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
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


def main():
    N, Q = map(int, input().split())

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


main()

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class UnionFind(object):
    def __init__(self, n, recursion = False):
        self._par = list(range(n))
        self._size = [1] * n
        self._recursion = recursion

    def root(self, k):
        if self._recursion:
            if k == self._par[k]:
                return k
            self._par[k] = self.root(self._par[k])
            return self._par[k]
        else:
            root = k
            while root != self._par[root]: root = self._par[root]
            while k != root: k, self._par[k] = self._par[k], root
            return root

    def unite(self, i, j):
        i, j = self.root(i), self.root(j)
        if i == j: return False
        if self._size[i] < self._size[j]: i, j = j, i
        self._par[j] = i
        self._size[i] += self._size[j]
        return True

    def is_connected(self, i, j):
        return self.root(i) == self.root(j)

    def size(self, k):
        return self._size[self.root(k)]

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

    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            uf.unite(u, v)
        else:
            print(int(uf.is_connected(u, v)))
resolve()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, N: int):
        """
        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: int) -> int:
        """頂点xの根を見つける"""
        if self.root[x] < 0:
            return x
        else:
            while self.root[x] >= 0:
                x = self.root[x]
            return x

    def union(self, x: int, y: int) -> int:
        """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: int, y: int) -> bool:
        """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)
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 UnionFind:
    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の根を見つける"""
        if self.root[x] < 0:
            return x
        else:
            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)
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:
def main():
    class UnionFind:
        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の根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                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())
    ans = [0, 1]
    uf = UnionFind(n)
    for i in range(q):
        t, u, v = map(int, input().split())
        if t:
            print(ans[uf.same(u, v)])
        else:
            uf.union(u, v)

main()

Submission status: Accepted

Solution code:
class UnionFind:
  r = None
  
  def __init__(self, n):
    self.r = list(range(n))
    
  def root(self, x):
    if(x == self.r[x]): return self.r[x]
    else: 
      self.r[x] = self.root(self.r[x])
      return self.r[x]
  
  def unite(self, x, y):
    if(self.root(x) == self.root(y)): return False
    else: self.r[self.root(x)] = self.root(y)
  
  def same(self, x, y):
    return (self.root(x) == self.root(y))
    
N, Q = list(map(int, input().split()))
UF = UnionFind(N)
for i in range(Q):
  t, u, v = list(map(int, input().split()))
  if(t == 0): UF.unite(u,v)
  else: print(int(UF.same(u,v)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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):
        """
        yをxの根に繋ぐ
        """
        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):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    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(u, v)))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
            return x
        else:
            a = x
            ul = []
            while a != self.__table[a]:
                ul.append(a)
                a = self.__table[a]
            for u in ul:
                self.__table[u] = a

        return self.__table[x]

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

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g


@mt
def slv(N, Q, TUV):
    uf = UnionFind()

    ans = []
    for t, u, v in TUV:
        if t == 1:
            ans.append(1 if uf.same(u, v) else 0)
        else:
            uf.union(u, v)

    return ans


def main():
    N, Q = read_int_n()
    TUV = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, TUV), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# UnionFind
class UnionFind:
  def __init__(self,n):
    self.n=n
    self.a=[-1]*n
    self.r=[0]*n
    self.siz=n
  def root_find(self,x):
    if self.a[x]<0:
      return x
    else:
      self.a[x]=self.root_find(self.a[x])
      return self.a[x]
  def unite(self,x,y):
    x=self.root_find(x)
    y=self.root_find(y)
    if x==y:
      return
    if self.r[x]==self.r[y]:
      self.r[x]+=1
      self.a[x]+=self.a[y]
      self.a[y]=x
    elif self.r[x]>self.r[y]:
      self.a[x]+=self.a[y]
      self.a[y]=x
    else:
      self.a[y]+=self.a[x]
      self.a[x]=y
    self.siz-=1
  def root_same(self,x,y):
      return self.root_find(x)==self.root_find(y)


n,q=map(int,input().split())
u=UnionFind(n)
for _ in range(q):
    t,a,b=map(int,input().split())
    if t==0:
        u.unite(a,b)
    else:
        print(u.root_same(a,b)+0)

Submission status: Accepted

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

        def find(self, x):
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                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)

    import sys
    n, q = map(int, sys.stdin.buffer.readline().split())
    uf = UnionFind(n)
    for _ in range(q):
        t, u, v = map(int, sys.stdin.buffer.readline().split())
        if t:
            print(int(uf.same(u, v)))
        else:
            uf.union(u, v)


main()

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

Submission status: Accepted

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

# UnionFind
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.a=[-1]*n
        self.siz=n
    def root_find(self,x):
        if self.a[x]<0:
            return x
        else:
            self.a[x]=self.root_find(self.a[x])
            return self.a[x]
    def unite(self,x,y):
        x=self.root_find(x)
        y=self.root_find(y)
        if x==y:
          return
        elif self.a[x]<self.a[y]:
            self.a[x]+=self.a[y]
            self.a[y]=x
        else:
            self.a[y]+=self.a[x]
            self.a[x]=y
        self.siz-=1
    def root_same(self,x,y):
        return self.root_find(x)==self.root_find(y)

n,q=map(int,input().split())
u=UnionFind(n)
for _ in range(q):
    t,a,b=map(int,input().split())
    if t==0:
        u.unite(a,b)
    else:
        print(u.root_same(a,b)+0)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

n,q = map(int,input().split())
U = Unionfind(n)
for i in range(q):
    t,u,v = map(int,input().split())
    if t == 0:
        U.union(u,v)
    else:
        print(int(U.same(u,v)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]
def main():
    n,q = map(int,input().split())
    U = Unionfind(n)
    for i in range(q):
        t,u,v = map(int,input().split())
        if t == 0:
            U.union(u,v)
        else:
            print(int(U.same(u,v)))

if __name__ == "__main__":
    main()