GC Mark Phase

Problem

Run the mark phase of a tracing garbage collector.

roots is the list of root object ids and edges is a list of [from, to] references. Starting from the roots, follow references transitively and collect every reachable object.

Return the reachable ids sorted in ascending order.

Hint

A visited set prevents infinite loops when references form cycles.

Test cases

case 1

in: [[1],[[1,2],[2,3],[4,5]]]

expected: [1,2,3]

case 2

in: [[],[[1,2]]]

expected: []

case 3

in: [[1,2],[]]

expected: [1,2]

case 4

in: [[1],[[1,1]]]

expected: [1]

case 5

in: [[1],[[1,2],[2,1]]]

expected: [1,2]

Starter codePython

def gc_mark(roots, edges):
    # Your code here
    pass

5 test cases · run your code against them in the editor