Directed cycle detection distinguishes unvisited, active and completed nodes. Reaching an active node indicates a back edge in the current search path.
Before you start
You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.
The practical goal is to reason through this situation: A dependency graph cycle appears when DFS revisits a node still on its recursion path. Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.
Step-by-step walkthrough
Step 1: Track three states
Unvisited, active and completed encode different traversal facts.
Step 2: Detect an active back edge
A neighbor active on the current recursion path indicates a directed cycle.
Step 3: Complete and restart
Clear active status on return and start other disconnected components.
Worked scenario
A dependency graph cycle appears when DFS revisits a node still on its recursion path.
A→B→C→A reaches active A and reveals a cycle. In A→B and A→C→B, B may already be completed when reached from C; that repeated visit is not a cycle. A single visited boolean cannot distinguish those cases.
Common mistake
A single visited flag cannot distinguish an active ancestor from a completed node.
Verify the behavior
Test both graphs, a self-loop and a disconnected cyclic component.
Interview exercise
Detect a directed cycle.
Answer and reasoning
Track active-path membership and clear it on completion, repeating the search for disconnected components.
Continue learning
Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.