A strong answer
In a directed graph, reaching an already-visited vertex doesn't prove a cycle: with edges 0 → 1, 0 → 2, 1 → 3 and 2 → 3, vertex 3 is reached twice but nothing loops. A cycle exists exactly when DFS reaches a vertex that is still on the current path.
So I track three colors. White: unvisited. Gray: entered, on the current path. Black: finished, all descendants explored. Entering a vertex turns it gray; after exploring all its neighbors it turns black. An edge to a gray vertex is a back edge, which closes a cycle; an edge to a black vertex is safe, because if a finished vertex could reach the current path, the search would already have found it from there. Running DFS from every white vertex covers the whole graph in O(V + E). To report the cycle, keep parent pointers and walk back from the current vertex to the gray one.
Alternatively, Kahn's algorithm: compute in-degrees, repeatedly remove vertices with in-degree 0 and decrement their neighbors. If some vertices never reach in-degree 0, they are on a cycle or downstream of one. It is also O(V + E), iterative so it can't overflow the stack, and it produces a topological order when there is no cycle.
Uses include package and build dependency checks, spreadsheet circular references, and deadlock detection, where an operating system or database looks for a cycle in a wait-for graph of transactions and locks.
What the interviewer is listening for
- Why a plain visited set gives false positives.
- The three-color DFS with a correct explanation of gray and black.
- Kahn's algorithm as an alternative, and O(V + E).
Common mistakes
- Using the undirected "visited and not the parent" rule on a directed graph.
- Resetting colors between DFS starts, which makes the algorithm quadratic.
- Treating any edge to a visited vertex as a cycle.