ABC392 E — Cables and Servers

1# -*- coding: utf-8 -*-2 3 4from typing import List5 6 7class UnionFind:8    """Represents a data structure that tracks a set of elements partitioned9       into a number of disjoint (non-overlapping) subsets.10 11    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.12 13    See:14    https://www.youtube.com/watch?v=zV3Ul2pA2Fw15    https://en.wikipedia.org/wiki/Disjoint-set_data_structure16    https://atcoder.jp/contests/abc120/submissions/444494217    https://atcoder.jp/contests/abc292/submissions/3941007518    https://github.com/not522/ac-library-python/blob/master/atcoder/dsu.py19    """20 21    def __init__(self, number_count: int) -> None:22        """23        Args:24            number_count: The size of elements (greater than 2).25        """26        self.number_count = number_count27        self.parent_numbers = [-1 for _ in range(number_count)]28 29    def find_root(self, number: int) -> int:30        """Follows the chain of parent pointers from number up the tree until31           it reaches a root element, whose parent is itself.32        Args:33            number: The trees id (0-index).34 35        Returns:36            The index of a root element.37        """38        if self.parent_numbers[number] < 0:39            return number40 41        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])42        return self.parent_numbers[number]43 44    def get_group_size(self, number: int) -> int:45        """46        Args:47            number: The trees id (0-index).48 49        Returns:50            The size of group.51        """52        return -self.parent_numbers[self.find_root(number)]53 54    def is_same_group(self, number_x: int, number_y: int) -> bool:55        """Represents the roots of tree number_x and number_y are in the same56           group.57        Args:58            number_x: The trees x (0-index).59            number_y: The trees y (0-index).60        """61        return self.find_root(number_x) == self.find_root(number_y)62 63    def merge_if_needs(self, number_x: int, number_y: int) -> bool:64        """Uses find_root to determine the roots of the tree number_x and65           number_y belong to. If the roots are distinct, the trees are combined66           by attaching the roots of one to the root of the other.67        Args:68            number_x: The trees x (0-index).69            number_y: The trees y (0-index).70        """71        x = self.find_root(number_x)72        y = self.find_root(number_y)73 74        if x == y:75            return False76 77        if self.parent_numbers[x] > self.parent_numbers[y]:78            x, y = y, x79 80        self.parent_numbers[x] += self.parent_numbers[y]81        self.parent_numbers[y] = x82        return True83 84    def get_roots(self) -> List[int]:85        return [i for i, x in enumerate(self.parent_numbers) if x < 0]86 87 88def main():89    import sys90 91    input = sys.stdin.readline92 93    n, m = map(int, input().split())94    uf = UnionFind(n)95    extras = []96 97    for i in range(m):98        ai, bi = map(int, input().split())99        ai -= 1100        bi -= 1101 102        if uf.is_same_group(ai, bi):103            extras.append((i, ai, bi))104        else:105            uf.merge_if_needs(ai, bi)106 107    roots = uf.get_roots()108    count = len(roots) - 1109    roots = set(roots)110    print(count)111 112    while len(roots) > 1:113        i, ai, bi = extras.pop()114 115        v = uf.find_root(ai)116        roots.discard(v)117        u = roots.pop()118 119        # つなぎ直した連結成分をrootsに追加120        uf.merge_if_needs(u, v)121        roots.add(uf.find_root(u))122 123        print(i + 1, ai + 1, u + 1)124 125 126if __name__ == "__main__":127    main()128