Problem context and objectives
Mission briefing
Expedition navigator · Safe camps and hazards form a connected world map
Find a valid route while marking every place already explored: Directed Loop.
Without visited state, the party loops forever or revisits expensive terrain.
How you win
- 1Recognize when Directed cycle detection by DFS colors matches the clues
- 2Keep this true after every move: gray nodes are exactly the active DFS ancestors and black nodes have no undiscovered cycle below them
- 3Reach the result within O(V + E) time and O(V) space
Rules and pressure
- Target cost: O(V + E) time and O(V) space
- State rule: gray nodes are exactly the active DFS ancestors and black nodes have no undiscovered cycle below them
Lesson 1 of 3
Treat the DFS path as a live signal. White is unseen, gray is active now, and black is fully checked.
Your call · Node 1 is gray when edge 3 to 1 is inspected. What does that prove?