ABC447 E — Divide Graph

1# -*- coding: utf-8 -*-2 3 4class UnionFind:5    """Represents a data structure that tracks a set of elements partitioned6       into a number of disjoint (non-overlapping) subsets.7 8    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.9 10    See:11    https://www.youtube.com/watch?v=zV3Ul2pA2Fw12    https://en.wikipedia.org/wiki/Disjoint-set_data_structure13    https://atcoder.jp/contests/abc120/submissions/444494214    https://atcoder.jp/contests/abc292/submissions/3941007515    https://github.com/not522/ac-library-python/blob/master/atcoder/dsu.py16    """17 18    def __init__(self, number_count: int) -> None:19        """20        Args:21            number_count: The size of elements (greater than 2).22        """23        self.number_count = number_count24        self.parent_numbers = [-1 for _ in range(number_count)]25        self.group_count = number_count26 27    def find_root(self, number: int) -> int:28        """Follows the chain of parent pointers from number up the tree until29           it reaches a root element, whose parent is itself.30        Args:31            number: The trees id (0-index).32 33        Returns:34            The index of a root element.35        """36        if self.parent_numbers[number] < 0:37            return number38 39        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])40        return self.parent_numbers[number]41 42    def is_same_group(self, number_x: int, number_y: int) -> bool:43        """Represents the roots of tree number_x and number_y are in the same44           group.45        Args:46            number_x: The trees x (0-index).47            number_y: The trees y (0-index).48        """49        return self.find_root(number_x) == self.find_root(number_y)50 51    def merge_if_needs(self, number_x: int, number_y: int) -> bool:52        """Uses find_root to determine the roots of the tree number_x and53           number_y belong to. If the roots are distinct, the trees are combined54           by attaching the roots of one to the root of the other.55        Args:56            number_x: The trees x (0-index).57            number_y: The trees y (0-index).58        """59        x = self.find_root(number_x)60        y = self.find_root(number_y)61 62        if x == y:63            return False64 65        self.group_count -= 166 67        if self.parent_numbers[x] > self.parent_numbers[y]:68            x, y = y, x69 70        self.parent_numbers[x] += self.parent_numbers[y]71        self.parent_numbers[y] = x72        return True73 74    def get_group_count(self) -> int:75        return self.group_count76 77 78def main():79    import sys80 81    input = sys.stdin.readline82 83    n, m = map(int, input().split())84    graph = []85    uf = UnionFind(n)86 87    for i in range(m):88        ai, bi = map(int, input().split())89        ai -= 190        bi -= 191        graph.append((ai, bi, i + 1))92 93    mod = 99824435394    ans = 095 96    for ui, vi, i in graph[::-1]:97        if uf.get_group_count() >= 3:98            uf.merge_if_needs(ui, vi)99        elif uf.get_group_count() == 2 and uf.is_same_group(ui, vi):100            pass101        else:102            ans += pow(2, i, mod)103            ans %= mod104 105    print(ans)106 107 108if __name__ == "__main__":109    main()110