DFS Finish Order

Problem

Return the postorder in which nodes finish during an iterative depth-first search.

edges is an undirected edge list, start is the DFS root, and neighbors are visited from smallest index to largest. A node enters the output only after all of its descendants have finished. Nodes unreachable from start never finish and are omitted.

Hint

Push a second copy of a node so it is appended after its children pop.

Test cases

case 1

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

expected: [2,1,0]

case 2

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

expected: [1,2,3,0]

case 3

in: [2,[],1]

expected: [1]

case 4

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

expected: [3,2]

Starter codePython

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

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