DSA interview question

Detect a Cycle in a Directed Graph (DFS)

Hard · Data structures · Topics: graph, dfs, cycle detection

The problem

A build system has tasks with "must run before" dependencies (directed edges). If the dependencies contain a cycle, the build can never start, so it must be detected up front. In a directed graph, meeting an already-visited vertex isn't enough to prove a cycle: in a diamond 0→1→3 and 0→2→3, vertex 3 is reached twice without any cycle. What matters is reaching a vertex that is still on the current DFS path. Use three colours: unvisited, on the stack (in progress) and done. An edge into an in-progress vertex is a back edge, which means a cycle.

Example: edges 0→1, 1→2, 2→0 → true; edges 0→1, 0→2, 1→3, 2→3 → false.

Function signature

bool isCyclic(int V, const vector<vector<int>>& adj);  // directed adjacency list

Test cases

Input `(V, edges)`	Output	Explanation
`(3, [[0,1],[1,2],[2,0]])`	`true`	0 → 1 → 2 → 0
`(4, [[0,1],[1,2],[2,3],[3,3]])`	`true`	A self-loop at 3
`(4, [[0,1],[0,2],[1,3],[2,3]])`	`false`	A diamond: 3 is reached twice, but there's no cycle
`(3, [[0,1],[1,2]])`	`false`
`(2, [[1,0]])`	`false`

(Confirm: edges are directed; the graph may be disconnected; self-loops count as cycles.)

How interviewers phrase it

"Given a directed graph, check whether it contains a cycle" (GeeksforGeeks "Detect cycle in a directed graph").

Clarifying questions to ask

Directed? (Yes, which is why the undirected parent trick doesn't apply.)
Can there be self-loops? (Yes, and each is a cycle.)
Can the graph be disconnected? (Yes.)

Follow-ups to expect

"Why isn't a visited array enough?"
"What do the three colours mean?"
"Why can a black vertex be ignored?"
"BFS alternative?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview