DFS Topological Order

Problem

Produce a topological order with depth-first search instead of Kahn's algorithm.

Visit start nodes in increasing index order and each node's out-neighbors in increasing index order, appending nodes to a postorder list when their recursion finishes. Reverse the postorder at the end. If a gray node is reached again a directed cycle exists, so return an empty list.

Hint

A node is finished only after every descendant completes; seeing a gray node means a cycle.

Test cases

case 1

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

expected: [0,2,1,3]

case 2

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

expected: []

case 3

in: [1,[]]

expected: [0]

case 4

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

expected: [3,0,1,2]

case 5

in: [3,[]]

expected: [2,1,0]

Starter codePython

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

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