Smallest Node on a Cycle

Problem

Find the lowest-index node that lies on at least one directed cycle.

edges is a list of directed [u, v] pairs and n is small, so a separate reachability check from each node is affordable. Node s lies on a cycle when some node in adj[s] can reach s again, which includes the self-loop case. Return the smallest such s, or -1 when the graph is a DAG.

Hint

A node is cyclic exactly when one of its out-neighbors can walk back to it.

Test cases

case 1

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

expected: 0

case 2

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

expected: 1

case 3

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

expected: -1

case 4

in: [3,[[2,2]]]

expected: 2

case 5

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

expected: -1

Starter codePython

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

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