Given an adjacency list graph (graph[i] is the array of neighbours of node i, and the graph can be directed) and a start node, return the nodes in the order a recursive depth-first search would visit them: visit a node, then try its neighbours in the listed order, going deep into each unvisited one before trying the next.
- Do not use recursion. The tests include a chain of 200,000 nodes, which overflows the call stack of a recursive version
- Only nodes reachable from
start appear in the result, each exactly once - The order matters: a simple stack of nodes that pushes all neighbours at once gives a different order for some graphs
- O(V + E) time