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:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
# 同一の集合の判定
def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False
# 集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

# 集合の数
def uCnt(x):
    return -par[find(x)]

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

for i in range(Q):
    tmp = list(map(int, input().split()))
    if tmp[0] == 0:
        unite(tmp[1], tmp[2])
    else:
        if same(tmp[1], tmp[2]):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


class UnionFind(object):
    '''Represents a data structure that tracks a set of elements partitioned
       into a number of disjoint (non-overlapping) subsets.
    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.
    See:
    https://www.youtube.com/watch?v=zV3Ul2pA2Fw
    https://en.wikipedia.org/wiki/Disjoint-set_data_structure
    https://atcoder.jp/contests/abc120/submissions/4444942
    '''

    def __init__(self, number_count: int):
        '''
        Args:
            number_count: The size of elements (greater than 2).
        '''
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        '''Follows the chain of parent pointers from number up the tree until
           it reaches a root element, whose parent is itself.
        Args:
            number: The trees id (0-index).
        Returns:
            The index of a root element.
        '''
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        '''
        Args:
            number: The trees id (0-index).
        Returns:
            The size of group.
        '''
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        '''Represents the roots of tree number_x and number_y are in the same
           group.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        '''Uses find_root to determine the roots of the tree number_x and
           number_y belong to. If the roots are distinct, the trees are combined
           by attaching the roots of one to the root of the other.
        Args:
            number_x: The trees x (0-index).
            number_y: The trees y (0-index).
        '''
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) >= self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


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

    for i in range(q):
        ti, ui, vi = map(int, input().split())

        if ti == 0:
            uf.merge_if_needs(ui, vi)
        else:
            if uf.is_same_group(ui, vi):
                print(1)
            else:
                print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, Q = map(int, input().split())
    uft = UnionFindTree(N)
    for _ in range(Q):
        t, u, v = map(int, input().split())
        if t == 0:
            uft.unite(u-1, v-1)
        else:
            print(1 if uft.is_same(u-1, v-1) else 0)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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())
TUV = [list(map(int, input().split())) for _ in range(q)]
  
uf = UnionFind(n)
for t, u, v in TUV:
  if t == 0:
    uf.union(u, v)
  else:
    print(1 if uf.same(u, v) else 0)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.n=n
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
    def find(self, x): # xの属する連結成分の代表元(leader)
        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,yを連結(merge)
        x = self.find(x)
        y = self.find(y)
        if x != y:
            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
    def same(self, x, y): # x,yが連結かどうか
        return self.find(x) == self.find(y)
    def size(self, x): # xと同じ連結成分のサイズ（ついでにUnionFind 1周）
        cnt=0
        parx=self.find(x)
        n=self.n
        for i in range(n):
            pari=self.find(i)
            if pari==parx:
                cnt+=1
        return cnt

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

Submission status: Accepted

Solution code:
N,Q = [int(i) for i in input().split()]
L = list(range(N))
for _ in range(Q):
  n,u,v = [int(i) for i in input().split()]
  while u != L[u]:
    u = L[u]
  while v != L[v]:
    v = L[v]
  u,v = [max(u,v),min(u,v)]
  if n == 0:
    L[u] = v
  else:
    if u == v:
      print(1)
    else:
      print(0)

Submission status: Accepted

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

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

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


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

Submission status: Accepted

Solution code:

def find(u , pre):
	pre[u] = (u if u == pre[u] else find(pre[u] , pre))
	return pre[u]

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

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)
    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        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


N,Q = MI()
UF = UnionFind(N)
for _ in range(Q):
    t,u,v = MI()
    if t == 0:
        UF.unite(u,v)
    else:
        print(1 if UF.same_check(u,v) else 0)

Submission status: Accepted

Solution code:
import sys

sys.path.append("/home/contestant/.local/lib/python3.8/site-packages")

import networkx as nx

N, Q = [int(x) for x in input().split()]
UF = nx.utils.UnionFind()
for t, u, v in [[int(x) for x in input().split()] for i in range(Q)]:
    if t == 0:
        UF.union(u, v)
    else:
        print(int(UF[u] == UF[v]))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]

def main():
    n, q = map(int, input().split())
    union = UnionFind(n)
    
    for i in range(q):
        query = list(map(int, input().split()))
        if query[0] == 0:
            union.union(query[1], query[2])
        else:
            print(int(union.same(query[1], query[2])))
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

class UF():
    def __init__(self, num):
        self.par = [-1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            stack = []
            while self.par[x] >= 0:
                stack.append(x)
                x = self.par[x]
            for xi in stack:
                self.par[xi] = x
            return x
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
        return rx

N, Q = map(int, readline().split())
 
T = UF(N)

Ans = []
for _ in range(Q):
    t, a, b = map(int, readline().split())
    if t == 0:
        T.union(a, b)
    else:
        Ans.append(int(T.find(a) == T.find(b)))
 
print('\n'.join(map(str, Ans)))

Submission status: Accepted

Solution code:
def solve(n, q, t, u, v):
    parents = list(range(n+1))
    def root(x):
        if x != parents[x]:
            parents[x] = root(parents[x])
        return parents[x]
    res = []
    for i in range(q):
        a = root(u[i])
        b = root(v[i])
        if t[i] == 0:
            if a > b:
                a, b = b, a
            parents[b] = a
        else:
            res.append(int(a == b))
    return "\n".join(map(str, res))

n, q = map(int, input().split())
t, u, v = zip(*[map(int, input().split()) for i in range(q)])
print(solve(n, q, t, 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))


def main() -> None:
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    import sys

    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:
from networkx.utils import UnionFind
N,Q=map(int,input().split())
uf = UnionFind()
for i in range(Q):
  t,u,v = map(int,input().split())
  if t:print(1 if uf[u]==uf[v] else 0)
  else:uf.union(u,v)

Submission status: Accepted

Solution code:
from networkx.utils import UnionFind

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

uf = UnionFind()
same = lambda v1,v2: uf.__getitem__(v1)==uf.__getitem__(v2)

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

Submission status: Accepted

Solution code:
import networkx as nx

N, Q = [int(x) for x in input().split()]
UF = nx.utils.UnionFind()
for t, u, v in [[int(x) for x in input().split()] for i in range(Q)]:
    if t == 0:
        UF.union(u, v)
    else:
        print(int(UF[u] == UF[v]))

Submission status: Accepted

Solution code:
import networkx as nx
def MAP(): return map(int, input().split())
n,q=MAP()
g=nx.utils.UnionFind(range(n))
for _ in range(q):
    t,u,v=MAP()
    if t==0:g.union(u,v)
    else:print(1 if g[u]==g[v] else 0)

Submission status: Accepted

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


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)
        self.rank = [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 isSame(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, Q = map(int, input().split())
uf = UF_tree(N + 1)
for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        uf.unite(u, v)
    else:
        if uf.isSame(u, v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import sys


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

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x, y = y, x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

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

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)

    def size(self, x: int) -> int:
        return -self.forest[self.findRoot(x)]

def main():
    input = sys.stdin.readline
    n,q = map(int,input().split())
    uf = UnionFind(n)
    for i in range(q):
        ti,ui,vi = map(int,input().split())
        if ti:
            print(int(uf.issame(ui,vi)))
        else:
            uf.union(vi,ui)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

    def union(self, x: int, y: int) -> None:
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            return
        if self.forest[x] > self.forest[y]:
            x, y = y, x
        self.forest[x] += self.forest[y]
        self.forest[y] = x
        return

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

    def issame(self, x: int, y: int) -> bool:
        return self.findRoot(x) == self.findRoot(y)

    def size(self, x: int) -> int:
        return -self.forest[self.findRoot(x)]


n,q = map(int,input().split())
uf = UnionFind(n)
for i in range(q):
    ti,ui,vi = map(int,input().split())
    if ti:
        print(int(uf.issame(ui,vi)))
    else:
        uf.union(vi,ui)

Submission status: Accepted

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

par=[-1 for i in range(n)]

def root(a):
    if par[a]<0:
        return a
    else:
        return root(par[a])

def size(a):
    return -par[root(a)]

def connect(a,b):
    a=root(a)
    b=root(b)
    if a==b:
        return False
    if size(a)<size(b):
        a,b=b,a
    par[a]+=par[b]
    par[b]=a
    return True

for i in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        connect(b,c)
    else:
        if root(b)==root(c):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class dsu:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

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

    def leader(self, a):
        assert 0 <= a and a < self._n
        if self.parent_or_size[a] < 0:
            return a
        else:
            self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

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

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


N, Q = map(int, input().split())
d = dsu(N)
ans = []
for _ in range(Q):
    t, u, v = map(int, input().split())
    if t:
        ans.append(int(d.same(u, v)))
    else:
        d.merge(u, v)

for val in ans:
    print(val)

Submission status: Accepted

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

Group = [i for i in range(N+1)] # グループ分け
Nodes = [1]*(N+1) # 各グループのノードの数

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
            
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)

for i in range(Q):
    t,u,v=map(int,input().split())
    if t==0:
        Union(u,v)
    else:
        if find(u)==find(v):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
class UnionFindVerSize():
    def __init__(self, N):
        self._parent = [n for n in range(0, N)]
        self._size = [1] * N

    def find_root(self, x):
        if self._parent[x] == x: return x
        self._parent[x] = self.find_root(self._parent[x])
        return self._parent[x]

    def unite(self, x, y):
        gx = self.find_root(x)
        gy = self.find_root(y)
        if gx == gy: return

        if self._size[gx] < self._size[gy]:
            self._parent[gx] = gy
            self._size[gy] += self._size[gx]
        else:
            self._parent[gy] = gx
            self._size[gx] += self._size[gy]

    def get_size(self, x):
        return self._size[self.find_root(x)]

    def is_same_group(self, x, y):
        return self.find_root(x) == self.find_root(y)

    def calc_group_num(self):
        N = len(self._parent)
        ans = 0
        for i in range(N):
            if self.find_root(i) == i:
                ans += 1
        return ans

import sys

input = sys.stdin.readline

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

uf = UnionFindVerSize(N)

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

    if t == 0:
        uf.unite(u-1,v-1)
    else:
        print(int(uf.is_same_group(u-1,v-1)))

Submission status: Accepted

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: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

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

    def unite(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        if xr == yr: return
        if self.size[xr] <= self.size[yr]:
            self.par[xr] = yr
            self.size[yr] += self.size[xr]
        else:
            self.par[yr] = xr
            self.size[xr] += self.size[yr]

import sys
input = sys.stdin.buffer.readline

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

uf = UnionFind(N)
res = list()

for _ in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        uf.unite(u, v)
    else:
        res.append(int(uf.find(u) == uf.find(v)))

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, q = map(int, input().split())
par = [-1]* n
rank = [0]*n
for i in range(q):
    t, u, v = map(int, input().split())
    if t == 0:
        Unite(u, v, par, rank)
    else:
        if Same(u, v, par):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    UNIONFIND_TABLE = []

    def unionfind_init(n):
        UNIONFIND_TABLE.append(np.full(n, -1, dtype=np.int64))
        return len(UNIONFIND_TABLE) - 1

    def unionfind_getroot(ins, x):
        table = UNIONFIND_TABLE[ins]
        stack = []
        while table[x] >= 0:
            stack.append(x)
            x = table[x]
        for y in stack:
            table[y] = x
        return x

    def unionfind_unite(ins, x, y):
        table = UNIONFIND_TABLE[ins]
        r1 = unionfind_getroot(ins, x)
        r2 = unionfind_getroot(ins, y)
        if r1 == r2:
            return
        d1 = table[r1]
        d2 = table[r2]
        if d1 <= d2:
            table[r2] = r1
            table[r1] += d2
        else:
            table[r1] = r2
            table[r2] += d1

    def unionfind_find(ins, x, y):
        return unionfind_getroot(ins, x) == unionfind_getroot(ins, y)

    def unionfind_getsize(ins, x):
        table = UNIONFIND_TABLE[ins]
        return -table[unionfind_getroot(ins, x)]

    n = inp[0]
    q = inp[1]
    ttt = inp[2::3]
    uuu = inp[3::3]
    vvv = inp[4::3]
    ins = unionfind_init(n)
    ans = []
    for i in range(q):
        if ttt[i] == 0:
            unionfind_unite(ins, uuu[i], vvv[i])
        else:
            ans.append(int(unionfind_find(ins, uuu[i], vvv[i])))
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from heapq import heappush,heappop
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input().rstrip()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007
# mod=998244353
inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')

file = 1




    
def solve():

    # k = ii()
    # for _ in range(ii()):
       
        
        n,q = mi()
        par = [i for i in range(n+1)]

        def find(u):
            if u==par[u]:
                return u
            par[u] = find(par[u])
            return par[u]

        def union(u,v):
            u = find(u)
            v = find(v)
            if u != v:
                par[v] = u

        for i in range(q):
            t,u,v = mi()
            if t==0:
                union(u,v)

            else:
                u = find(u)
                v = find(v)
                print(1 if u==v else 0)        


















        

    




        
if __name__ =="__main__":

    if(file):

        if path.exists('input.txt'):
            sys.stdin=open('input.txt', 'r')
            sys.stdout=open('output.txt','w')
        else:
            input=sys.stdin.readline

    # for _ in range(ii()):
    solve()