ABC293 D — Tying Rope

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    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.8    See:9    https://www.youtube.com/watch?v=zV3Ul2pA2Fw10    https://en.wikipedia.org/wiki/Disjoint-set_data_structure11    https://atcoder.jp/contests/abc120/submissions/444494212    https://atcoder.jp/contests/abc292/submissions/3941007513    '''14 15    def __init__(self, number_count: int):16        '''17        Args:18            number_count: The size of elements (greater than 2).19        '''20        self.parent_numbers = [-1 for _ in range(number_count)]21        self.edge_count = [0 for _ in range(number_count)]22        self.group_count = number_count23 24    def find_root(self, number: int) -> int:25        '''Follows the chain of parent pointers from number up the tree until26           it reaches a root element, whose parent is itself.27        Args:28            number: The trees id (0-index).29        Returns:30            The index of a root element.31        '''32        if self.parent_numbers[number] < 0:33            return number34 35        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])36        return self.parent_numbers[number]37 38    def get_group_size(self, number: int) -> int:39        '''40        Args:41            number: The trees id (0-index).42        Returns:43            The size of group.44        '''45        return -self.parent_numbers[self.find_root(number)]46 47    def is_same_group(self, number_x: int, number_y: int) -> bool:48        '''Represents the roots of tree number_x and number_y are in the same49           group.50        Args:51            number_x: The trees x (0-index).52            number_y: The trees y (0-index).53        '''54        return self.find_root(number_x) == self.find_root(number_y)55 56    def merge_if_needs(self, number_x: int, number_y: int) -> bool:57        '''Uses find_root to determine the roots of the tree number_x and58           number_y belong to. If the roots are distinct, the trees are combined59           by attaching the roots of one to the root of the other.60        Args:61            number_x: The trees x (0-index).62            number_y: The trees y (0-index).63        '''64        x = self.find_root(number_x)65        y = self.find_root(number_y)66 67        self.edge_count[x] += 168 69        if x == y:70            return False71 72        self.group_count -= 173 74        if self.parent_numbers[x] > self.parent_numbers[y]:75            x, y = y, x76 77        self.parent_numbers[x] += self.parent_numbers[y]78        self.parent_numbers[y] = x79        self.edge_count[x] += self.edge_count[y]80        return True81 82    def get_roots(self):83        return [i for i, x in enumerate(self.parent_numbers) if x < 0]84 85    def get_edge_count(self, number: int) -> int:86        return self.edge_count[number]87 88    def get_group_count(self) -> int:89        return self.group_count90 91 92def main():93    import sys94 95    input = sys.stdin.readline96 97    n, m = map(int, input().split())98    uf = UnionFind(n)99    x = 0100 101    for _ in range(m):102        ai, _, ci, _ = input().rstrip().split()103        ai, ci = int(ai) - 1, int(ci) - 1104 105        if uf.is_same_group(ai, ci):106            x += 1107        else:108            uf.merge_if_needs(ai, ci)109    110    print(x, uf.get_group_count() - x)111    112 113if __name__ == "__main__":114    main()115