ABC266 F — Well-defined Path Queries on a Namori

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    '''13 14    def __init__(self, number_count: int):15        '''16        Args:17            number_count: The size of elements (greater than 2).18        '''19        self.parent_numbers = [-1 for _ in range(number_count)]20 21    def find_root(self, number: int) -> int:22        '''Follows the chain of parent pointers from number up the tree until23           it reaches a root element, whose parent is itself.24        Args:25            number: The trees id (0-index).26        Returns:27            The index of a root element.28        '''29        if self.parent_numbers[number] < 0:30            return number31 32        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])33        return self.parent_numbers[number]34 35    def get_group_size(self, number: int) -> int:36        '''37        Args:38            number: The trees id (0-index).39        Returns:40            The size of group.41        '''42        return -self.parent_numbers[self.find_root(number)]43 44    def is_same_group(self, number_x: int, number_y: int) -> bool:45        '''Represents the roots of tree number_x and number_y are in the same46           group.47        Args:48            number_x: The trees x (0-index).49            number_y: The trees y (0-index).50        '''51        return self.find_root(number_x) == self.find_root(number_y)52 53    def merge_if_needs(self, number_x: int, number_y: int) -> bool:54        '''Uses find_root to determine the roots of the tree number_x and55           number_y belong to. If the roots are distinct, the trees are combined56           by attaching the roots of one to the root of the other.57        Args:58            number_x: The trees x (0-index).59            number_y: The trees y (0-index).60        '''61        x = self.find_root(number_x)62        y = self.find_root(number_y)63 64        if x == y:65            return False66 67        if self.get_group_size(x) >= self.get_group_size(y):68            self.parent_numbers[x] += self.parent_numbers[y]69            self.parent_numbers[y] = x70        else:71            self.parent_numbers[y] += self.parent_numbers[x]72            self.parent_numbers[x] = y73        return True74 75 76def main():77    import sys78 79    input = sys.stdin.readline80    sys.setrecursionlimit(10 ** 8)81 82    n = int(input())83    graph = [[] for _ in range(n)]84    uv = list()85    86    for _ in range(n):87        ai, bi = map(int, input().split())88        ai -= 189        bi -= 190    91        graph[ai].append(bi)92        graph[bi].append(ai)93 94        uv.append((ai, bi))95    96    visited = [False] * n97    on_cycle = [False] * n98    no_cycle = -199    100    # サイクルをdfsで検出101    def dfs(vertex, parent=-1):102        if visited[vertex]:103            return vertex104        105        visited[vertex] = True106 107        for to in graph[vertex]:108            if to == parent:109                continue110 111            r = dfs(to, vertex)112 113            if r == no_cycle:114                continue115 116            on_cycle[vertex] = True117 118            if r == vertex:119                return no_cycle120 121            return r122        123        return no_cycle124 125    dfs(0)126    127    uf = UnionFind(n)128 129    # サイクルの頂点を根とする木を構築130    for ui, vi in uv:131        if on_cycle[ui] and on_cycle[vi]:132            continue133 134        uf.merge_if_needs(ui, vi)135    136    q = int(input())137    ans = ["No"] * q138 139    # 同じ連結成分なら、単純パスが一意に定まる140    for i in range(q):141        xi, yi = map(int, input().split())142        xi -= 1143        yi -= 1144 145        if uf.is_same_group(xi, yi):146            ans[i] = "Yes"147    148    print(*ans, sep="\n")149 150 151if __name__ == "__main__":152    main()153