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:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
        self.tree = [True] * n
        self.grpcnt = n

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

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

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        self.grpcnt -= 1
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N, Q = MAP()
uf = UnionFind(N)
for i in range(Q):
    t, u, v = MAP()
    if t == 0:
        uf.union(u, v)
    else:
        ans = int(uf.is_same(u, v))
        print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True

    def same(self, x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
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.unite(u,v)

Submission status: Accepted

Solution code:
belong=list()
group=list()

def init(X):
  global belong
  global group
  belong=list(range(X))
  group=[[i] for i in range(X)]

def unite(x,y):
  if len(group[belong[x]])<len(group[belong[y]]):
    x,y=y,x
  if belong[x]==belong[y]:
    return True
  z=belong[y]
  for i in range(len(group[z])):
    belong[group[z][-1]]=belong[x]
    group[belong[x]].append(group[z][-1])
    del group[z][-1]
  return False

N,Q=map(int,input().split())
init(N)
f,u,v=0,0,0
for i in range(Q):
  f,u,v=map(int,input().split())
  if f:
    print((belong[u]==belong[v])+0)
  else:
    unite(u,v)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

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

uf_t = numba.types.UniTuple(i8[:], 2)


@njit((uf_t, i8), cache=True)
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit((uf_t, i8, i8), cache=True)
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8, i8, i8[:]), cache=True)
def main(N, Q, TUV):
    root = np.arange(N, dtype=np.int64)
    size = np.ones(N, np.int64)
    uf = (root, size)
    for i in range(Q):
        t, u, v = TUV[3 * i:3 * i + 3]
        if t == 0:
            merge(uf, u, v)
        else:
            same = find_root(uf, u) == find_root(uf, v)
            print(1 if same else 0)

N, Q = map(int, readline().split())
TUV = np.array(read().split(), np.int64)

main(N, Q, TUV)

Submission status: Accepted

Solution code:
# 参考URL https://note.nkmk.me/python-union-find/
class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

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

    uf = UnionFind(n)

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

main()

Submission status: Accepted

Solution code:
# 参考URL https://note.nkmk.me/python-union-find/
class UnionFind():
    # 各要素の親要素の番号を格納するリスト
    # 要素が根（ルート）の場合は-(そのグループの要素数)を格納する
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

def main():
    from sys import stdin
    input = stdin.buffer.readline

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

    uf = UnionFind(n)

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

main()

Submission status: Accepted

Solution code:
class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: #aのほうが大きい
                self.parent[b] = a
            else:
                self.parent[a] = b #bのほうが大きい
        
    def same(self, a, b):
        return self.find(a) == self.find(b)


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    ans = []
    uf = UnionFind(N)
    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))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: #aのほうが大きい
                self.parent[b] = a
            else:
                self.parent[a] = b #bのほうが大きい
        
    def same(self, a, b):
        return self.find(a) == self.find(b)


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    tuvs = map(int, sys.stdin.buffer.read().split())
    ans = []
    uf = UnionFind(N)
    for t, u, v in zip(tuvs, tuvs, tuvs):
        if t:
            ans.append('1' if uf.same(u, v) else '0')
        else:
            uf.union(u, v)

    print('\n'.join(ans))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.p = [-1] * n
        self.size = [1] * n
    def root(self, x):
        st = set()
        while(self.p[x] >= 0):
            st.add(x)
            x = self.p[x]
            for y in st:
                self.p[y] = x
        return x
    def find(self, x, y):
        return self.root(x) == self.root(y)
    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 != r2:
            p1 = self.p[r1]
            p2 = self.p[r2]
            if p1 <= p2:
                self.p[r2] = r1
                self.size[r1] += self.size[r2]
                if p1 == p2:
                    self.p[r1] -= 1
            else:
                self.p[r1] = r2
                self.size[r2] += self.size[r1]

N, Q = map(int, input().split())
uft = UnionFind(N)
for q in range(Q):
    t, u, v = map(int, input().split())
    if t == 0:
        uft.union(u, v)
    else:
        print(1 if uft.find(u, v) else 0)

Submission status: Accepted

Solution code:
class dsu:
    def __init__(self, n=0):
        self._n = n
        self.parent_or_size = [-1] * n
    
    def merge(self, a: int, b: int) -> int:
        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:
        return self.leader(a) == self.leader(b)
    
    def leader(self, a: int) -> int:
        x = a
        while self.parent_or_size[x] >= 0:
            x = self.parent_or_size[x]
        while a != x:
            self.parent_or_size[a], a = x, self.parent_or_size[a]
        return x
    
    def size(self, a: int) -> int:
        return -self.parent_or_size[self.leader(a)]
    
    def groups(self):
        g = [[] for _ in range(self._n)]
        for i in range(self._n):
            g[self.leader(i)].append(i)
        return list(c for c in g if c)

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

Submission status: Accepted

Solution code:
# verify-helper: PROBLEM https://judge.yosupo.jp/problem/unionfind
import sys

input = sys.stdin.buffer.readline


class UnionFindTree:
    """Disjoint-Set Data Structure

    Union-Find Tree

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """
    __slots__ = ["par", "rank"]

    def __init__(self, n: int) -> None:
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

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

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


def main() -> None:
    N, Q = map(int, input().split())
    uft = UnionFindTree(N)
    ans = []
    for _ in range(Q):
        t, u, v = map(int, input().split())
        if t == 0:
            uft.unite(u, v)
        else:
            ans.append(int(uft.is_same(u, v)))
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# verify-helper: PROBLEM https://judge.yosupo.jp/problem/unionfind
import sys

input = sys.stdin.buffer.readline


class UnionFindTree:
    """Disjoint-Set Data Structure

    Union-Find Tree

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n: int) -> None:
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

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

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


def main() -> None:
    N, Q = map(int, input().split())
    uft = UnionFindTree(N)
    ans = []
    for _ in range(Q):
        t, u, v = map(int, input().split())
        if t == 0:
            uft.unite(u, v)
        else:
            ans.append(int(uft.is_same(u, v)))
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
class dsu:
    def __init__(self, n=0):
        self._n = n
        self.parent_or_size = [-1] * n
    
    def merge(self, a: int, b: int) -> int:
        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:
        return self.leader(a) == self.leader(b)
    
    def leader(self, a: int) -> int:
        x = a
        while self.parent_or_size[x] >= 0:
            x = self.parent_or_size[x]
        while a != x:
            self.parent_or_size[a], a = x, self.parent_or_size[a]
        return x
    
    def size(self, a: int) -> int:
        return -self.parent_or_size[self.leader(a)]
    
    def groups(self):
        g = [[] for _ in range(self._n)]
        for i in range(self._n):
            g[self.leader(i)].append(i)
        return list(c for c in g if c)

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

Submission status: Accepted

Solution code:
# verify-helper: PROBLEM https://judge.yosupo.jp/problem/unionfind
import sys

input = sys.stdin.buffer.readline


class UnionFindTree:
    """Disjoint-Set Data Structure

    Union-Find Tree

    complexity:
        - init: O(n)
        - find, unite, same: O(alpha(n))
    """

    def __init__(self, n: int) -> None:
        self.par = list(range(n))  # parent
        self.rank = [0] * n  # depth of tree

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

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


def main() -> None:
    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, v)
        else:
            print(int(uft.is_same(u, v)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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):
        self.all_group_member=defaultdict(list)
        for i in range(self.n):
            self.all_group_member[self.find(i)].append(i)
        return self.all_group_member

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

def main():
    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(1 if uf.same(u,v) else 0)



if __name__ == '__main__':
    main()

Submission status: Accepted

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(1 if f==b else 0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

# dsu / UnionFind


def init_unionfind(N):
    global parent, rank
    parent = [-1] * N
    rank = [0] * N


def find_root_1(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def find_root(x):
    p = parent[x]
    while p != -1:
        x = p
        p = parent[x]
    return x


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))

# acl/dsu


init = init_unionfind
merge = unite
# FIXME: return value

same = is_connected
leader = find_root


def size(a):
    raise NotImplementedError


def group(a):
    raise NotImplementedError
# ---


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    # parse input
    N, Q = map(int, input().split())
    init(N)
    for _q in range(Q):
        q, u, v = map(int, input().split())
        if q == 0:
            merge(u, v)
        else:
            print(int(same(u, v)))


# tests
T1 = """
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
0
1
0
1
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

# dsu / UnionFind


def init_unionfind(N):
    global parent, rank
    parent = [-1] * N
    rank = [0] * N


def find_root(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))

# acl/dsu


init = init_unionfind
merge = unite
# FIXME: return value

same = is_connected
leader = find_root


def size(a):
    raise NotImplementedError


def group(a):
    raise NotImplementedError
# ---


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    # parse input
    N, Q = map(int, input().split())
    init(N)
    for _q in range(Q):
        q, u, v = map(int, input().split())
        if q == 0:
            merge(u, v)
        else:
            print(int(same(u, v)))


# tests
T1 = """
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
0
1
0
1
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

# dsu / UnionFind


def init_unionfind(N):
    global parent, rank
    parent = [-1] * N
    rank = [0] * N


def find_root(x):
    p = parent[x]
    if p == -1:
        return x
    p2 = find_root(p)
    parent[x] = p2
    return p2


def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if x == y:
        return  # already united
    if rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1


def is_connected(x, y):
    return (find_root(x) == find_root(y))

# acl/dsu


def init(n):
    init_unionfind(n)


def merge(a, b):
    unite(a, b)
    # FIXME: return value


def same(a, b):
    return is_connected(a, b)


def leader(a):
    return find_root(a)


def size(a):
    raise NotImplementedError


def group(a):
    raise NotImplementedError
# ---


def debug(*x):
    print(*x, file=sys.stderr)


def main():
    # parse input
    N, Q = map(int, input().split())
    init(N)
    for _q in range(Q):
        q, u, v = map(int, input().split())
        if q == 0:
            merge(u, v)
        else:
            print(int(same(u, v)))


# tests
T1 = """
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
0
1
0
1
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
def union(x,y):
    par[x]+=par[y]
    par[y]=x
    


def find(a):
    ans=[]
    while par[a]>=0:
        ans.append(a)
        a=par[a]
    for i in ans:
        par[i]=a
    return a



n,q=map(int,input().split())
par={i:-1 for i in range(n)}
for _ in range(q):
    a,b,c=map(int,input().split())
    if a==0:
        x,y=find(b),find(c)
        if x!=y:
            union(x,y)
    else:
        x,y=find(b),find(c)
        if x==y:
            print('1')
        else:
            print('0')