ABC401 E — Reachable Set

1# -*- coding: utf-8 -*-2 3from typing import List4 5 6class UnionFind:7    """Represents a data structure that tracks a set of elements partitioned8       into a number of disjoint (non-overlapping) subsets.9 10    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.11 12    See:13    https://www.youtube.com/watch?v=zV3Ul2pA2Fw14    https://en.wikipedia.org/wiki/Disjoint-set_data_structure15    https://atcoder.jp/contests/abc120/submissions/444494216    https://atcoder.jp/contests/abc292/submissions/3941007517    https://github.com/not522/ac-library-python/blob/master/atcoder/dsu.py18    """19 20    def __init__(self, number_count: int) -> None:21        """22        Args:23            number_count: The size of elements (greater than 2).24        """25        self.number_count = number_count26        self.parent_numbers = [-1 for _ in range(number_count)]27        self.edge_count = [0 for _ in range(number_count)]28        self.group_count = number_count29 30    def find_root(self, number: int) -> int:31        """Follows the chain of parent pointers from number up the tree until32           it reaches a root element, whose parent is itself.33        Args:34            number: The trees id (0-index).35 36        Returns:37            The index of a root element.38        """39        if self.parent_numbers[number] < 0:40            return number41 42        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])43        return self.parent_numbers[number]44 45    def get_group_size(self, number: int) -> int:46        """47        Args:48            number: The trees id (0-index).49 50        Returns:51            The size of group.52        """53        return -self.parent_numbers[self.find_root(number)]54 55    def is_same_group(self, number_x: int, number_y: int) -> bool:56        """Represents the roots of tree number_x and number_y are in the same57           group.58        Args:59            number_x: The trees x (0-index).60            number_y: The trees y (0-index).61        """62        return self.find_root(number_x) == self.find_root(number_y)63 64    def merge_if_needs(self, number_x: int, number_y: int) -> bool:65        """Uses find_root to determine the roots of the tree number_x and66           number_y belong to. If the roots are distinct, the trees are combined67           by attaching the roots of one to the root of the other.68        Args:69            number_x: The trees x (0-index).70            number_y: The trees y (0-index).71        """72        x = self.find_root(number_x)73        y = self.find_root(number_y)74 75        self.edge_count[x] += 176 77        if x == y:78            return False79 80        self.group_count -= 181 82        if self.parent_numbers[x] > self.parent_numbers[y]:83            x, y = y, x84 85        self.parent_numbers[x] += self.parent_numbers[y]86        self.parent_numbers[y] = x87        self.edge_count[x] += self.edge_count[y]88        return True89 90    def get_roots(self) -> List[int]:91        return [i for i, x in enumerate(self.parent_numbers) if x < 0]92 93    def get_groups(self) -> List[List[int]]:94        roots: List[int] = [self.find_root(i) for i in range(self.number_count)]95        groups: List[List[int]] = [[] for _ in range(self.number_count)]96 97        for i in range(self.number_count):98            groups[roots[i]].append(i)99 100        return list(filter(lambda g: g, groups))101 102    def get_edge_count(self, number: int) -> int:103        return self.edge_count[number]104 105    def get_group_count(self) -> int:106        return self.group_count107 108 109def main():110    import sys111 112    input = sys.stdin.readline113 114    n, m = map(int, input().split())115    graph = [[] for _ in range(n)]116 117    for _ in range(m):118        ai, bi = map(int, input().split())119        ai -= 1120        bi -= 1121 122        graph[ai].append(bi)123        graph[bi].append(ai)124 125    uf_small = UnionFind(n)126    uf_large = UnionFind(n)127    ans = list()128 129    for i in range(n):130        for j in graph[i]:131            if i > j:132                uf_small.merge_if_needs(i, j)133            else:134                uf_large.merge_if_needs(i, j)135 136        k = i + 1137 138        if uf_small.get_group_size(0) == k:139            ans += [uf_large.get_group_size(0) - k]140        else:141            ans += [-1]142 143    print(*ans, sep="\n")144 145 146if __name__ == "__main__":147    main()148