DSA interview question

Detect a Cycle in a Directed Graph (Topological Sort)

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

The problem

A package installer resolves dependencies (edge u → v means u must be installed before v) and must refuse to install if the dependencies are circular. Kahn's topological sort doubles as a cycle detector. Vertices on a directed cycle never reach in-degree 0, because each one waits for the previous vertex on the cycle. So if the algorithm outputs fewer than V vertices, a cycle exists.

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

Function signature

bool hasCycleKahn(int V, const vector<vector<int>>& adj);

Test cases

Input `(V, edges)`	Output	Explanation
`(4, [[0,1],[1,2],[2,0],[2,3]])`	`true`	0, 1, 2 never become ready
`(5, [[0,1],[1,2],[2,3],[3,4],[4,1]])`	`true`	The cycle 1-2-3-4
`(1, [[0,0]])`	`true`	A self-loop
`(4, [[0,1],[0,2],[1,3],[2,3]])`	`false`	A diamond is acyclic
`(3, [])`	`false`

(Confirm: edges are directed; self-loops and multiple components are allowed.)

How interviewers phrase it

"Detect a cycle in a directed graph using topological sort (BFS / Kahn's algorithm)" (GeeksforGeeks).

Clarifying questions to ask

Directed? (Yes.)
Do I need the cycle itself or just a yes/no? (Yes/no.)
Can the graph be disconnected? (Yes. Kahn's handles that naturally.)

Follow-ups to expect

"Why do cycle vertices never reach in-degree 0?"
"What exactly remains unprocessed?"
"How would you find an actual cycle?"
"Kahn vs DFS colouring?"
"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