DSA interview question

Detect a Cycle in an Undirected Graph (DFS)

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

The problem

A package manager builds an undirected "compatibility" graph between modules and must flag any circular compatibility chain. With DFS, go deep from a vertex, and remember the vertex you came from. If you ever meet an already-visited vertex other than the one you just came from, you've found a back edge, which closes a cycle. Run the DFS from every unvisited vertex, since the graph may be disconnected.

Example: 6 vertices, edges 0-1, 1-2, 3-4, 4-5, 5-3 → true (the cycle is in the second component).

Function signature

bool isCycleDFS(int V, const vector<vector<int>>& adj);  // simple undirected graph

Test cases

Input `(V, edges)`	Output	Explanation
`(6, [[0,1],[1,2],[3,4],[4,5],[5,3]])`	`true`	Triangle 3-4-5
`(4, [[0,1],[1,2],[2,3],[3,0]])`	`true`	A square
`(5, [[0,1],[0,2],[0,3],[0,4]])`	`false`	A star is a tree
`(3, [[0,1],[1,2]])`	`false`	A path
`(1, [])`	`false`

(Confirm: the graph is simple (no self-loops or parallel edges) and may be disconnected.)

How interviewers phrase it

"Detect a cycle in an undirected graph using DFS" (GeeksforGeeks).

Clarifying questions to ask

Disconnected graphs? (Yes, so DFS from every unvisited vertex.)
A simple graph? (Assume yes.)
Recursion limits? (For large graphs, an iterative DFS with (vertex, parent) pairs avoids stack overflow.)

Follow-ups to expect

"What's a back edge?"
"Why pass the parent?"
"How does this differ for directed graphs?"
"Counting check?"
"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