Iterative DFS Visit Order

core

You are given a directed graph on nodes 0 through n-1 as an adjacency list adj, where adj[u] lists the nodes reachable from u by one edge (follow edges only in the direction given). Implement dfs_order_iter(n, adj, src) returning exactly the order a recursive depth-first search from src first reaches nodes (the order graph-dfs-recursive defines), but with an explicit stack and no recursion.

The discipline is visit-on-pop. Pop u; if it is already visited, discard it and pop again; otherwise mark it, record it, and push all of adj[u] in reverse order, so the first-listed neighbor ends up on top and pops first. A node may sit on the stack several times, and that is not sloppiness, it is the algorithm: the copy pushed by the deepest, most recently explored ancestor must win, and the stale copies below get discarded by the visited check when their turn comes.

If you drilled bfs-dist, its mark-on-push discipline is the exact habit to leave at the door. Marking at push time is right for BFS, where the first discovery is the one that counts, and wrong here: it freezes each node at its first, shallowest discovery, so a node the source lists late pops in source-neighbor position even when an earlier branch reaches it deep and recursion would visit it there. Mark-on-push produces a plausible-looking order and agrees with recursion on every tree, which is exactly why the fumble survives.

Example: dfs_order_iter(4, {{1,2,3}, {3}, {}, {}}, 0) returns {0, 1, 3, 2}: from 0 the search descends into 1, finds 3 there, and only then unwinds to visit 2. Mark-on-push returns {0, 1, 2, 3} on the same graph: 3 was marked the moment 0 pushed it, so the copy 1 would push is refused and 3 waits at the bottom of the stack.

Input format: each test in tests/*.in is laid out as:

Line 1: n e, the node count and the number of directed edges; nodes are numbered 0 to n - 1.
Next e lines: u v, one directed edge from u to v. When e is 0 there are no edge lines.
Last line: s, the start node passed to dfs_order_iter.

Test 01.in reads:

1 0
0

This is the smallest case: 1 node, 0 edges, start at node 0. Line 2 is already the start node, not an edge.

Where you'll use it:

✦ Solution & editorial unlock with the pass.