ABC304 E — Good 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    """16 17    def __init__(self, number_count: int):18        """19        Args:20            number_count: The size of elements (greater than 2).21        """22        self.parent_numbers = [-1 for _ in range(number_count)]23        self.edge_count = [0 for _ in range(number_count)]24        self.group_count = number_count25 26    def find_root(self, number: int) -> int:27        """Follows the chain of parent pointers from number up the tree until28           it reaches a root element, whose parent is itself.29        Args:30            number: The trees id (0-index).31 32        Returns:33            The index of a root element.34        """35        if self.parent_numbers[number] < 0:36            return number37 38        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])39        return self.parent_numbers[number]40 41    def get_group_size(self, number: int) -> int:42        """43        Args:44            number: The trees id (0-index).45 46        Returns:47            The size of group.48        """49        return -self.parent_numbers[self.find_root(number)]50 51    def is_same_group(self, number_x: int, number_y: int) -> bool:52        """Represents the roots of tree number_x and number_y are in the same53           group.54        Args:55            number_x: The trees x (0-index).56            number_y: The trees y (0-index).57        """58        return self.find_root(number_x) == self.find_root(number_y)59 60    def merge_if_needs(self, number_x: int, number_y: int) -> bool:61        """Uses find_root to determine the roots of the tree number_x and62           number_y belong to. If the roots are distinct, the trees are combined63           by attaching the roots of one to the root of the other.64        Args:65            number_x: The trees x (0-index).66            number_y: The trees y (0-index).67        """68        x = self.find_root(number_x)69        y = self.find_root(number_y)70 71        self.edge_count[x] += 172 73        if x == y:74            return False75 76        self.group_count -= 177 78        if self.parent_numbers[x] > self.parent_numbers[y]:79            x, y = y, x80 81        self.parent_numbers[x] += self.parent_numbers[y]82        self.parent_numbers[y] = x83        self.edge_count[x] += self.edge_count[y]84        return True85 86    def get_roots(self):87        return [i for i, x in enumerate(self.parent_numbers) if x < 0]88 89    def get_edge_count(self, number: int) -> int:90        return self.edge_count[number]91 92    def get_group_count(self) -> int:93        return self.group_count94 95 96def main():97    import sys98    from collections import defaultdict99 100    input = sys.stdin.readline101 102    n, m = map(int, input().split())103    uf = UnionFind(n)104 105    for _ in range(m):106        ai, bi = map(int, input().split())107        ai -= 1108        bi -= 1109 110        if not uf.is_same_group(ai, bi):111            uf.merge_if_needs(ai, bi)112 113    k = int(input())114 115    ng = defaultdict(int)116 117    for i in range(k):118        xi, yi = map(int, input().split())119        xi -= 1120        yi -= 1121 122        ng[(uf.find_root(xi), uf.find_root(yi))] += 1123 124    q = int(input())125 126    for _ in range(q):127        pi, qi = map(int, input().split())128        pi -= 1129        qi -= 1130 131        pi_p, qi_p = uf.find_root(pi), uf.find_root(qi)132 133        if ng[(pi_p, qi_p)] > 0 or ng[(qi_p, pi_p)] > 0:134            print("No")135        else:136            print("Yes")137 138 139if __name__ == "__main__":140    main()141