Editorial for Bad Trees

Use this editorial only when stuck, and do not 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$ nodes. For each proposed edge $(a, b)$ :

If $a$ and $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)$ time, which is fine for $e \le 5 \times 10^5$ .

Solution (Python)

Code 1

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)

Comments0

No comments yet

Be the first to comment.

Editorial for Bad Trees

Approach

Solution (Python)

Comments0

New comment