Recursive 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; self-loops and repeated edges are allowed). Implement dfs_order(n, adj, src) returning the nodes in the order a recursive depth-first search starting at src first reaches them: visit src, then for each v in adj[u] in the order given, descend into v if it has not been visited yet. Nodes not reachable from src are left out entirely, and every node appears at most once.

The visited mark is the whole mechanic. Mark a node the moment the search enters it, before iterating its neighbors, and let the source be marked the same way every other node is. A graph with a cycle leading back to a node you have already entered is the case that exposes a mark placed in the wrong spot, and it is exactly the case a hand-traced acyclic example never reaches.

Example: dfs_order(5, {{1,2}, {3}, {3}, {}, {}}, 0) returns {0, 1, 3, 2}. From 0 the search descends to 1 and then to 3, which has no neighbors; it unwinds to 0, descends to 2, and finds 3 already visited. Node 4 is unreachable, so it never appears.

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.
Last line: s, the start node passed to dfs_order.

Test 06.in reads:

3 1
1 2
0

This is 3 nodes and 1 edge (1 -> 2), starting from node 0, which touches neither endpoint: the traversal visits only node 0.

Where you'll use it:

✦ Solution & editorial unlock with the pass.