Problem:


Score : 100 points

Problem Statement

You are given an undirected graph with N vertices and 0 edges. Process Q queries of the following types.

0 u v: Add an edge (u, v).

1 u v: Print 1 if u and v are in the same connected component, 0 otherwise.

Constraints

1 \leq N \leq 200,000

1 \leq Q \leq 200,000

0 \leq u_i, v_i \lt N

Input

Input is given from Standard Input in the following format:

N Q
t_1 u_1 v_1
t_2 u_2 v_2
:
t_Q u_Q v_Q

出力

For each query of the latter type, print the answer.

Sample Input 1

4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3

Sample Output 1

0
1
0
1



Sample input:
4 7
1 0 1
0 0 1
0 2 3
1 0 1
1 1 2
0 0 2
1 1 3


Sample output:
0
1
0
1

Submission status: Accepted

Solution code:
from typing import List


class UnionFind:
    """Union Find (Disjoint Set): O(α(N))
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp
        https://tumoiyorozu.github.io/single-file-ac-library/document_en/dsu.html
    """

    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x in O(α(n)) amortized."""
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> List[int]:
        """Return the set of groups (roots) in O(n)."""
        return [i for i, r in enumerate(self._roots) if r < 0]

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected in O(α(n)) amortized."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y in O(α(n)) amortized."""
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

    def get_size(self, x: int) -> int:
        """Return the size of the group where vertex x belongs in O(α(n)) amortized."""
        return -self._roots[self[x]]


def unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    import sys

    read = sys.stdin.buffer.read

    N, Q, *TUV = map(int, read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


def arc032_b():
    # https://atcoder.jp/contests/arc032/tasks/arc032_2
    N, M, *AB = map(int, open(0).read().split())
    tree = UnionFind(N + 1)
    for a, b in zip(*[iter(AB)] * 2):
        tree.unite(a, b)
    print(len(tree) - 2)


if __name__ == "__main__":
    unionfind()
    # arc032_b()

Submission status: Accepted

Solution code:
class UnionFind:
    """Union Find (Disjoint Set): O(α(N))
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp
        https://tumoiyorozu.github.io/single-file-ac-library/document_en/dsu.html
    """

    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x in O(α(n)) amortized."""
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected in O(α(n)) amortized."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y in O(α(n)) amortized."""
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x


import sys

readline = sys.stdin.buffer.readline

N, Q = map(int, readline().split())
tree = UnionFind(N)
res = []
for _ in range(Q):
    t, u, v = map(int, readline().split())
    if t:
        res.append(int(tree.is_connected(u, v)))
    else:
        tree.unite(u, v)
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
from typing import List


class UnionFind:
    """Union Find (Disjoint Set): O(α(N))
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp
        https://tumoiyorozu.github.io/single-file-ac-library/document_en/dsu.html
    """

    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x in O(α(n)) amortized."""
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> List[int]:
        """Return the set of groups (roots) in O(n)."""
        return [i for i, r in enumerate(self._roots) if r < 0]

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected in O(α(n)) amortized."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y in O(α(n)) amortized."""
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

    def get_size(self, x: int) -> int:
        """Return the size of the group where vertex x belongs in O(α(n)) amortized."""
        return -self._roots[self[x]]


import sys

readline = sys.stdin.buffer.readline

N, Q = map(int, readline().split())
tree = UnionFind(N)
res = []
for _ in range(Q):
    t, u, v = map(int, readline().split())
    if t:
        res.append(int(tree.is_connected(u, v)))
    else:
        tree.unite(u, v)
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
from typing import List


class UnionFind:
    """Union Find (Disjoint Set): O(α(N))
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp
        https://tumoiyorozu.github.io/single-file-ac-library/document_en/dsu.html
    """

    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x in O(α(n)) amortized."""
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> List[int]:
        """Return the set of groups (roots) in O(n)."""
        return [i for i, r in enumerate(self._roots) if r < 0]

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected in O(α(n)) amortized."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y in O(α(n)) amortized."""
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

    def get_size(self, x: int) -> int:
        """Return the size of the group where vertex x belongs in O(α(n)) amortized."""
        return -self._roots[self[x]]


def unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    import sys

    readline = sys.stdin.buffer.readline

    N, Q = map(int, readline().split())
    tree = UnionFind(N)
    res = []
    for _ in range(Q):
        t, u, v = map(int, readline().split())
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


def arc032_b():
    # https://atcoder.jp/contests/arc032/tasks/arc032_2
    N, M, *AB = map(int, open(0).read().split())
    tree = UnionFind(N + 1)
    for a, b in zip(*[iter(AB)] * 2):
        tree.unite(a, b)
    print(len(tree) - 2)


if __name__ == "__main__":
    unionfind()
    # arc032_b()

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]

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

    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def unite(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        elif self._roots[y] < self._roots[x]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

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


import sys

readline = sys.stdin.buffer.readline

N, Q = map(int, readline().split())
tree = UnionFind(N)
res = []
for _ in range(Q):
    t, u, v = map(int, readline().split())
    if t:
        res.append(int(tree.is_connected(u, v)))
    else:
        tree.unite(u, v)
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]

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

    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def unite(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        elif self._roots[y] < self._roots[x]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

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


import sys

read = sys.stdin.buffer.read

N, Q, *TUV = map(int, read().split())
tree = UnionFind(N)
res = []
for t, u, v in zip(*[iter(TUV)] * 3):
    if t:
        res.append(int(tree.is_connected(u, v)))
    else:
        tree.unite(u, v)
print("\n".join(map(str, res)))

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]

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

    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def unite(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        elif self._roots[y] < self._roots[x]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

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


def main():
    import sys

    read = sys.stdin.buffer.read

    N, Q, *TUV = map(int, read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from typing import List


class UnionFind:
    """Union Find (Disjoint Set): O(α(N))
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp
        https://tumoiyorozu.github.io/single-file-ac-library/document_en/dsu.html
    """

    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x in O(α(n)) amortized."""
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected in O(α(n)) amortized."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y in O(α(n)) amortized."""
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x


def unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    import sys

    read = sys.stdin.buffer.read

    N, Q, *TUV = map(int, read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    unionfind()

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]

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

    def __getitem__(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def unite(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        elif self._roots[y] < self._roots[x]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

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


def main():
    N, Q, *TUV = map(int, open(0).read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from typing import List


class UnionFind:
    """Union Find (Disjoint Set): O(α(N))
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp
        https://tumoiyorozu.github.io/single-file-ac-library/document_en/dsu.html
    """

    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x in O(α(n)) amortized."""
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected in O(α(n)) amortized."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y in O(α(n)) amortized."""
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x


def unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    N, Q, *TUV = map(int, open(0).read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    unionfind()

Submission status: Accepted

Solution code:
class UnionFind:
    __slots__ = ["_data_size", "_roots"]

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

    def find(self, x):
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self._roots[y] < self._roots[x]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

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


def main():
    N, Q, *TUV = map(int, open(0).read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from typing import Set


class UnionFind:
    """Union Find (Disjoint Set): O(α(N))
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp
        https://tumoiyorozu.github.io/single-file-ac-library/document_en/dsu.html
    """

    __slots__ = ["_data_size", "_roots"]

    def __init__(self, data_size: int) -> None:
        self._data_size = data_size
        self._roots = [-1] * data_size

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x in O(α(n)) amortized."""
        while self._roots[x] >= 0:
            x = self._roots[x]
        return x

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> Set[int]:
        """Return the set of groups (roots) in O(n)."""
        return {i for i, r in enumerate(self._roots) if r < 0}

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected in O(α(n)) amortized."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y in O(α(n)) amortized."""
        x, y = self[x], self[y]
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

    def get_size(self, x: int) -> int:
        """Return the size of the group vertex x belongs in O(α(n)) amortized."""
        return -self._roots[self[x]]


def unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    N, Q, *TUV = map(int, open(0).read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    unionfind()

Submission status: Accepted

Solution code:
from typing import Set


class UnionFind:
    """Union Find (Disjoint Set): O(α(N))
    References:
        https://github.com/atcoder/ac-library/blob/master/atcoder/dsu.hpp
        https://tumoiyorozu.github.io/single-file-ac-library/document_en/dsu.html
    """

    __slots__ = ["_data_size", "_first_idx", "_roots"]

    def __init__(self, data_size: int, is_zero_origin: bool = True) -> None:
        self._data_size = data_size
        self._first_idx = 0 if is_zero_origin else 1
        self._roots = [-1] * (data_size + self._first_idx)

    # def __getitem__(self, x: int) -> int:
    #     """Find the group (root) of vertex x."""
    #     while self._roots[x] >= 0:
    #         x = self._roots[x]
    #     return x

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> Set[int]:
        """Return the set of groups (roots)."""
        return {
            self._find(x)
            for x in range(self._first_idx, self._data_size + self._first_idx)
        }

    def _find(self, x: int) -> int:
        while self._roots[x] >= 0:
            x = self._roots[x]

        return x

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected or not."""
        return self._find(x) == self._find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self._find(x), self._find(y)
        if x == y:
            return
        if self._roots[x] > self._roots[y]:
            x, y = y, x
        self._roots[x] += self._roots[y]
        self._roots[y] = x

    def unite_all(self, *vertices: int) -> None:
        """Unite the groups of all of the given vertices."""
        x = vertices[0]
        for y in vertices[1:]:
            self.unite(x, y)

    def get_size(self, x: int) -> int:
        """Return the size of the group vertex x belongs."""
        return -self._roots[self._find(x)]


def unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    N, Q, *TUV = map(int, open(0).read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    unionfind()

Submission status: Accepted

Solution code:
from typing import Set


class UnionFind:
    """Union-Find: O(α(N))"""

    __slots__ = ["_data_size", "_first_idx", "_parents"]

    def __init__(self, data_size: int, is_zero_origin: bool = True) -> None:
        self._data_size = data_size
        self._first_idx = 0 if is_zero_origin else 1
        self._parents = [-1] * (data_size + self._first_idx)

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x."""
        while self._parents[x] >= 0:
            x = self._parents[x]

        return x

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> Set[int]:
        """Return the set of groups (roots)."""
        return {
            self[x] for x in range(self._first_idx, self._data_size + self._first_idx)
        }

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected or not."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self[x], self[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 unite_all(self, *vertices: int) -> None:
        """Unite the groups of all of the given vertices."""
        x = vertices[0]
        for y in vertices[1:]:
            self.unite(x, y)

    def get_size(self, x: int) -> int:
        """Return the size of the group vertex x belongs."""
        return -self._parents[self[x]]


def unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    N, Q, *TUV = map(int, open(0).read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    unionfind()

Submission status: Accepted

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

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

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

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

    def union(self, x, y):
        """x, yが属する木をunion"""
        # 根を比較する
        # すでに同じ木に属していた場合は何もしない.
        # 違う木に属していた場合はrankを見てくっつける方を決める.
        # rankが同じ時はrankを1増やす
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.root[y] < self.root[x]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x

    def same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return -self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) if x < 0]

    def group_count(self):
        """連結成分の数"""
        return len(self.roots())

    def all_group_members(self):
        """{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す"""
        return {r: self.members(r) for r in self.roots()}


def main():
    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)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    """Union-Find: O(α(N))"""

    __slots__ = ["_data_size", "_first_idx", "_parents"]

    def __init__(self, data_size: int, is_zero_origin: bool = True) -> None:
        self._data_size = data_size
        self._first_idx = 0 if is_zero_origin else 1
        self._parents = [-1] * (data_size + self._first_idx)

    def _find(self, x: int) -> int:
        if self._parents[x] < 0:
            return x
        self._parents[x] = self._find(self._parents[x])
        return self._parents[x]

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected or not."""
        return self._find(x) == self._find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self._find(x), 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 unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    # https://atcoder.jp/contests/practice2/tasks/practice2_a
    N, Q, *TUV = map(int, open(0).read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    unionfind()

Submission status: Accepted

Solution code:
from typing import Set


class UnionFind:
    """Union-Find: O(α(N))"""

    __slots__ = ["_data_size", "_first_idx", "_parents"]

    def __init__(self, data_size: int, is_zero_origin: bool = True) -> None:
        self._data_size = data_size
        self._first_idx = 0 if is_zero_origin else 1
        self._parents = [-1] * (data_size + self._first_idx)

    def __getitem__(self, x: int) -> int:
        """Find the group (root) of vertex x."""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self[self._parents[x]]
        return self._parents[x]

    def __len__(self) -> int:
        """Count the number of groups (roots)."""
        return len(self.groups)

    @property
    def groups(self) -> Set[int]:
        """Return the set of groups (roots)."""
        return {
            self[x] for x in range(self._first_idx, self._data_size + self._first_idx)
        }

    def is_connected(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are connected or not."""
        return self[x] == self[y]

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self[x], self[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 unite_all(self, *vertices: int) -> None:
        """Unite the groups of all of the given vertices."""
        x = vertices[0]
        for y in vertices[1:]:
            self.unite(x, y)

    def get_size(self, x: int) -> int:
        """Return the size of the group vertex x belongs."""
        return -self._parents[self[x]]


def unionfind():
    # https://judge.yosupo.jp/problem/unionfind
    N, Q, *TUV = map(int, open(0).read().split())
    tree = UnionFind(N)
    res = []
    for t, u, v in zip(*[iter(TUV)] * 3):
        if t:
            res.append(int(tree.is_connected(u, v)))
        else:
            tree.unite(u, v)
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    unionfind()

Submission status: Accepted

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

    def find(self, x):
        """ 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）"""
        tmp = []
        parents = self.parents
        while parents[x] >= 0:
            tmp.append(x)
            x = parents[x]
        for y in tmp:
            parents[y] = x
        return 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 same(self, x, y):
        """ xとyが同じ根の子かを判定 """
        return self.find(x) == self.find(y)

    def size(self, x):
        """ xの根のparent（= 要素数）を返す """
        return -self.parents[self.find(x)]

    def members(self, x):
        """ xが属するグループの要素をリストとして返す """
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        """ 全ての根の要素をリストとして返す """
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        """ グループの数を返す """
        return len(self.roots())

    def size_list(self):
        """ 各グループの要素数のリストを返す(根の番号は返さない) """
        return [-x for x in self.parents if x < 0]

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


##############################################################################################################
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
U = UnionFind(N)
for _ in range(M):
    t, a, b = map(int, input().split())
    if t==0: U.union(a, b)
    else: print(int(U.same(a, b)))