Editorial for Bad Trees

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

This is a classic online cycle check. Maintain a disjoint-set union (DSU) over the $n$ ~n~ nodes. For each proposed edge $(a, b)$ ~(a, b)~:

If $a$ ~a~ and $b$ ~b~ are already in the same component, adding the edge would create a cycle, so answer No.
Otherwise answer Yes and unite the two components.

With union by size and path compression this runs in nearly $O(n + e)$ ~O(n + e)~ time, which is fine for $e \le 5 \times 10^5$ ~e \le 5 \times 10^5~.

Solution (Python)

class DisjointSet():

    def __init__(self,size : int) -> None:
        self.parent = [i for i in range(size)]
        self.size = list[int](1 for _ in range(size))

    def find_set(self,v : int) -> int:

        if (self.parent[v] == v): return v

        parent = self.find_set(self.parent[v])
        self.parent[v] = parent
        return parent

    def union(self,v : int, u : int) -> None:

        a = self.find_set(v)
        b = self.find_set(u)

        if a == b: return

        if (self.size[a] > self.size[b] ): a,b = b,a

        self.parent[a] = b
        self.size[b] += self.size[a]

n,e = (int(x) for x in input().split())

dsu = DisjointSet(n+1)

for _ in range(e):
    a,b = (int(x) for x in input().split())

    if dsu.find_set(a) == dsu.find_set(b):
        print("No")
    else:
        print("Yes")
        dsu.union(a,b)

Comments

There are no comments at the moment.