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: Wrong Answer

Solution code:
def find(u, tree_root):
    tree_root[u] = u if u == tree_root[u] else find(tree_root[u], tree_root)
    return tree_root[u]

def main():
    n, q = map(int, input().split())
    tree_root = list(range(n))
    for i in range(q):
        t, u, v = map(int, input().split())
        u_root, v_root = find(u, tree_root), find(v, tree_root)
        if t:
            print(1 if u_root == v_root else 0)
        else:
            tree_root[u] = v_root

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)


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

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

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x != y:
            if self.par[x] > self.par[y]:  # merge technique
                x, y = y, x
            self.par[x] += self.par[y]
            self.par[y] = x

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

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


n, q = map(int, input().split())
uf = UnionFind(n)
for _ in range(q):
    t, u, v = map(int, input().split())
    u -= 1
    v -= 1
    if t == 0:
        # add
        uf.unite(u, v)
    else:
        print(1 if uf.same(u, v) else 0)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, length):
        self.parent_indexes = [-1]* length
        
    def union(self, i, j):
        if i == j:
            return
        # iが所属する集団のサイズ>=jが所属する集団のサイズにする
        if self.get_group_size(i) < self.get_group_size(j):
            i, j = j, i
        self.parent_indexes[i] = - self.get_group_size(i) - self.get_group_size(j)
        self.parent_indexes[j] = self.find(i)
        
    # i番目の要素が所属する集団の親nodeのindexを返す
    # メモ化もする
    def find(self, i):
        if self.parent_indexes[i] < 0:
            return i
        parent_index = self.find(self.parent_indexes[i])
        self.parent_indexes[i] = parent_index
        return parent_index

    def get_group_size(self, i):
        return - self.parent_indexes[self.find(i)]
    
    def are_in_the_same_group(self, i, j):
        return self.find(i) == self.find(j)
    
    
n, q = list(map(lambda x: int(x), input().split()))
uf = UnionFind(n)
for _ in range(q):
    t, u, v = list(map(lambda x: int(x), input().split()))
#     print(uf.parent_indexes)
    if t == 0:
        uf.union(u, v)
        continue
    print('1') if uf.are_in_the_same_group(u, v) else print('0')

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, length):
        self.parent_indexes = [-1]* length
        
    def union(self, i, j):
        if i == j:
            return
        # iが所属する集団のサイズ>=jが所属する集団のサイズにする
        if self.get_group_size(i) < self.get_group_size(j):
            i, j = j, i
        self.parent_indexes[i] = - self.get_group_size(i) - self.get_group_size(j)
        self.parent_indexes[j] = self.parent_indexes[i]
        
    # i番目の要素が所属する集団の親nodeのindexを返す
    # メモ化もする
    def find(self, i):
        if self.parent_indexes[i] < 0:
            return i
        parent_index = self.find(self.parent_indexes[i])
        self.parent_indexes[i] = parent_index
        return parent_index

    def get_group_size(self, i):
        return - self.parent_indexes[self.find(i)]
    
    def are_in_the_same_group(self, i, j):
        return self.find(i) == self.find(j)
    
    
n, q = list(map(lambda x: int(x), input().split()))
uf = UnionFind(n)
for _ in range(q):
    t, u, v = list(map(lambda x: int(x), input().split()))
#     print(uf.parent_indexes)
    if t == 0:
        uf.union(u, v)
        continue
    print('1') if uf.are_in_the_same_group(u, v) else print('0')

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, length):
        self.parent_indexes = [-1]* length
        
    def union(self, i, j):
        if i == j:
            return
        # iが所属する集団のサイズ>=jが所属する集団のサイズにする
        if self.get_group_size(i) < self.get_group_size(j):
            i, j = j, i
        self.parent_indexes[i] = - self.get_group_size(i) - self.get_group_size(j)
        self.parent_indexes[j] = i
        
    # i番目の要素が所属する集団の親nodeのindexを返す
    # メモ化もする
    def find(self, i):
        if self.parent_indexes[i] < 0:
            return i
#         parent_index = self.find(i)
#         parent_index = self.find(self.parent_indexes[i])
        parent_index = self.find(self.parent_indexes[i])
        self.parent_indexes[i] = parent_index
        return parent_index

    def get_group_size(self, i):
        return - self.parent_indexes[self.find(i)]
    
    def are_in_the_same_group(self, i, j):
        return self.find(i) == self.find(j)
    
    
n, q = list(map(lambda x: int(x), input().split()))
uf = UnionFind(n)
for _ in range(q):
    t, u, v = list(map(lambda x: int(x), input().split()))
#     print(uf.parent_indexes)
    if t == 0:
        uf.union(u, v)
        continue
    print('1') if uf.are_in_the_same_group(u, v) else print('0')

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
nei = {}
for _ in range(q):
  t, u, v = map(int, input().split())
  if t == 0:
    if u not in nei:
      nei[u] = set()
    if v not in nei:
      nei[v] = set()
    nei[u].add(v)
    nei[v].add(u)
  else:
    stack = [u]
    visited = set()
    flag = False
    while stack:
      node = stack.pop()
      visited.add(node)
      if not nei.get(node, None):
        continue
      for next_node in nei[node]:
        if next_node in visited:
          continue
        if next_node == v:
          flag = True
          break
        stack.append(next_node)
      if flag:
        break
    if flag:
      print(1)
    else:
      print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

links = defaultdict(set)
n, q = list(map(lambda x: int(x), input().split()))
for _ in range(q):
    t, u, v = list(map(lambda x: int(x), input().split()))
    if t == 0:
        links[min(u, v)].add(max(u, v))
        links[v].add(u)
        continue
    print('1') if max(u, v) in links[min(u, v)] else print('0')

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
set_list = []
for _ in range(q):
  t, u, v = map(int, input().split())
  if t == 0:
    flag = False
    if not set_list:
      set_list.append(set([u, v]))
      continue
    for ele in set_list:
      if u in ele:
        ele.add(v)
        flag = True
        break
      if v in ele:
        ele.add(u)
        flag = True
        break
    if not flag:
      set_list.append(set([u, v]))
  else:
    if not set_list:
      print(0)
      continue
    flag = False
    for ele in set_list:
      if u in ele:
        if v in ele:
          flag = True
        break
    if flag:
      print(1)
    else:
      print(0)

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
nei = {}
for i in range(n):
  nei[i] = set()
for _ in range(q):
  t, u, v = map(int, input().split())
  if t == 0:
    nei[u].add(v)
    nei[v].add(u)
  else:
    if v in nei[u] and u in nei[v]:
      print(1)
    else:
      print(0)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: language_level=3,  boundscheck=False, wraparound=False , cdivision=True
cdef extern from "/opt/atcoder-stl/atcoder/fenwicktree.hpp" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

from libc.stdio cimport scanf, printf
cdef int n, q, i, a, t, u, v
scanf('%d%d', &n, &q)
cdef fenwick_tree[long] *bit = new fenwick_tree[long](n)
for i in range(n):
    scanf('%d', &a)
    bit.add(i, a)
for i in range(q):
    scanf('%d%d%d', &t, &u, &v)
    if t:
        printf('%ld\n', bit.sum(u, v))
    else:
        bit.add(u, v)
"""
import os
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())

Link = []
Query = []
for i in range(Q):
	Query = list(map(int,input().split()))
	if Query[0] == 0:
		Link.append(Query[1:2])
	else:
		if Query[1:2] in Link:
			print('1')
		else:
			print('0')

Submission status: Wrong Answer

Solution code:
p=[-1]*8**6
for q in[open(0)][1:]:
 q,*x=map(int,q.split());a,b=sorted(map(f:=lambda x:f(p[x])if~p[x]<0else x,x))
 if q:print(+(a==b))
 elif a<b:p[b]=a

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
edges = []
ans = []

for i in range(q):
    t, u, v = map(int, input().split())
    if t == 1:
        if [u, v] in edges:
            ans.append(1)
        else:
            ans.append(0)
    else:
        edges.append([u, v])


for i in ans:
    print(i)

Submission status: Wrong Answer

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

for i in range(q):
    t, u, v = map(int, input().split())
    if t == 1:
        if [u, v] in edges:
            print(1)
        else:
            print(0)
    else:
        edges.append([u, v])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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) -> int:
    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 i in range(q):
    t, u, v = map(int, input().split())
    if t:
        print(int(find(u) == find(v)))
    else:
        union(u, v)

Submission status: Wrong Answer

Solution code:
from networkx.utils.union_find import UnionFind
n,q=map(int,input().split())
a=[[int(i) for i in input().split()] for _ in range(q)]

uf=UnionFind()
for i in range(n):
     uf.union(i,i)
for x in a:
     if x[0]==0:
          uf.union(x[1],x[2])
     else:
          f=x[1]
          while True:
               if f==uf.parents[f]:break
               f=uf.parents[f]
          b=x[2]
          while True:
               if b==uf.parents[b]:break
               b=uf.parents[b]
          print(0 if f==b else 1)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
        self.member_num = [1 for _ in range(size)]
 
    #representative
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        m1=self.member_num[s1]
        m2=self.member_num[s2]
        if s1 != s2:
            if m1 != m2:
                if m1 < m2:
                    self.table[s1] = s2
                    self.member_num[s2]=m1+m2
                    return [m1,m2]
                else:
                    self.table[s2] = s1
                    self.member_num[s1]=m1+m2
                    return [m1,m2]
            else:
                self.table[s1] = -1
                self.table[s2] = s1
                self.member_num[s1] = m1+m2
                return [m1,m2]
        return [0,0]

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.union(u-1,v-1)
    else:
        if uf.find(u-1)==uf.find(v-1):
            print(1)
        else:
            print(0)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
nei = {}
for _ in range(q):
  t, u, v = map(int, input().split())
  if t == 0:
    if u not in nei:
      nei[u] = set()
    if v not in nei:
      nei[v] = set()
    nei[u].add(v)
    nei[v].add(u)
  else:
    flag = False
    stack = set()
    visited = set()
    stack.add(u)
    while stack:
      node = stack.pop()
      if node in visited:
        continue
      if node == v:
        flag = True
        break
      visited.add(node)
      if not nei.get(node, None):
        continue
      for next_node in nei[node]:
        stack.add(next_node)
    if flag:
      print(1)
    else:
      print(0)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
nei = {}
for i in range(n):
  nei[i] = set()
for _ in range(q):
  t, u, v = map(int, input().split())
  if t == 0:
    nei[u].add(v)
    nei[v].add(u)
  else:
    stack = [u]
    visited = set()
    flag = False
    while stack:
      node = stack.pop()
      if node in visited:
        continue
      if node == v:
        flag = True
        break
      visited.add(node)
      for next_node in nei[node]:
        stack.append(next_node)
    if flag:
      print(1)
    else:
      print(0)

Submission status: Time Limit Exceeded

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

def union(a,b):
    a=find(a)
    b=find(b)
    if a==b:
        return 
    else:
        parents[a]=b

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: Time Limit Exceeded

Solution code:
import networkx as nx
 
n, q = map(int, input().split())
 
G = nx.Graph()
G.add_nodes_from([i for i in range(n)])
for i in range(q):
  t, u, v = map(int, input().split())
  if t == 0:
    G.add_edge(u, v)
  else:
    if nx.has_path(G, source=u, target=v):
      print(1)
    else:
      print(0)

Submission status: Time Limit Exceeded

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)
        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: Time Limit Exceeded

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
        while not 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


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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


class DisjointSetUnion:
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
        self.rank = [0] * n

    def root(self, x):
        if self.par[x] == -1:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[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.rank[x] < self.rank[y]:
            x, y = y, x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        return


if __name__ == '__main__':
    n, q = map(int, readline().split())
    dsu = DisjointSetUnion(n)

    for i in range(q):
        t, u, v = map(int, readline().split())

        if t:
            print(int(dsu.same(u, v)))
        else:
            dsu.unite(u, v)

Submission status: Accepted

Solution code:
class DisjointSetUnion:
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n
        self.rank = [0] * n

    def root(self, x):
        if self.par[x] == -1:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[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.rank[x] < self.rank[y]:
            x, y = y, x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        return

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

    for i in range(q):
        t, u, v = map(int, input().split())

        if t:
            print(int(dsu.same(u, v)))
        else:
            dsu.unite(u, v)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import networkx as nx
def input(): return sys.stdin.readline().rstrip()

def main():
    n,q = map(int, input().split())
    uf=nx.utils.UnionFind()
    for _ in range(q):
        t,u,v=map(int, input().split())
        if t==0:
            uf.union(u,v)
        else:
            print(1 if uf[u]==uf[v] else 0)
 
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import Iterable
import sys
def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    uf = UnionFindTree(N)
    for _ in range(Q):
        t, u, v = map(int, input().split())
        if t == 0:
            uf.union(u, v)
        else:
            print(1 if uf.same(u, v) else 0)

class UnionFindTree:
    __slots__ = ('parent')

    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

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

    def size(self, x: int) -> int:
        return -self.parent[self.find(x)]

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import Iterable
import sys
def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    uf = UnionFindTree(N)
    ans = []
    for _ in range(Q):
        t, u, v = map(int, input().split())
        if t:
            ans.append('1' if uf.same(u, v) else '0')
        else:
            uf.union(u, v)
    print('\n'.join(ans))

class UnionFindTree:
    __slots__ = ('parent')

    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

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

    def size(self, x: int) -> int:
        return -self.parent[self.find(x)]

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import Iterable
import sys
def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    uf = UnionFindTree(N)
    for _ in range(Q):
        t, u, v = map(int, input().split())
        if t == 0:
            uf.union(u, v)
        else:
            print(1 if uf.same(u, v) else 0)

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

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

    def size(self, x: int) -> int:
        return -self.parent[self.find(x)]

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
par = list(range(n))
size = [1] * n
def find(x):
    """ 根のノードの値を見つけて返す """
    if x != par[x]:
        par[x] = find(par[x])
    return par[x]

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

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

def same(x, y):
    """ xとyが同じ集合に属しているか """
    return find(x) == find(y)

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

Submission status: Accepted

Solution code:

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

    def same(self,x,y):
        return  self[x] == self[y]

    def find_max(self):
        return max(self.size)


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

uf = UnionFind(N)
merge = uf.merge
same = uf.same

for i in range(Q):
    t,a,b = map(int, input().split())
    if t:
        print(int(same(a,b)))

    else:
        merge(a,b)

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

import sys
input = sys.stdin.readline

# from atcoder.dsu import DSU

n, q = map(int,input().split())
C = [list(map(int,input().split())) for i in range(q)]

D = DSU(n)
for i in range(q):
    if C[i][0] == 0:
        D.merge(C[i][1], C[i][2])
    else:
        print(int(D.same(C[i][1], C[i][2])))

Submission status: Accepted

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

    def __init__(self, N):
        self.N = N
        self.root = [-1] * N


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

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

    def __init__(self, N):
        self.N = N
        self.root = [-1] * N

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


import sys
input = sys.stdin.readline


def main():
    n, q = map(int, input().split())
    uf = UnionFind(n)
    res = []
    for _ 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)))


main()