Baseline Graphs · Learning O(V + E) · O(V)
A tunnel inspector starts at junction 0 and always takes the first unexplored tunnel ahead of her, following corridors to their dead ends before backtracking to the last junction with options left. Her hand-written log — one entry per junction, in the order first entered — is the depth-first record of the cave system.
Input: An adjacency list adj for a connected undirected graph — adj[i] lists the neighbours of vertex i.
Output: Return the DFS order starting from vertex 0, exploring neighbours in the order they appear in each list.
1 <= V <= 10^5The graph is connected and undirected0 <= adj[i][j] < VInput: {"adj":[[1,2],[0,2],[0,1,3,4],[2],[2]]}
Output: [0,1,2,3,4]
The walk dives 0 -> 1 -> 2 -> 3, backtracks, then finishes with 4.
Input: {"adj":[[1,4],[0,2,3],[1,3],[1,2,4],[0,3]]}
Output: [0,1,2,3,4]
Each neighbour list is consumed left to right; 4 only fires after 3 is exhausted.