Reference Cycle Detection

Problem

Detect whether a directed graph of object references contains a cycle.

n is the number of objects and edges is a list of [from, to] references. A reference cycle means reference counting alone can never free the objects, so it must be found by a graph traversal.

Return True when a cycle exists, otherwise False.

Hint

Track visiting versus visited states so back edges reveal cycles.

Test cases

case 1

in: [3,[[0,1],[1,2],[2,0]]]

expected: true

case 2

in: [3,[[0,1],[1,2]]]

expected: false

case 3

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

expected: true

case 4

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

expected: true

case 5

in: [0,[]]

expected: false

Starter codePython

def has_reference_cycle(n, edges):
    # Your code here
    pass

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