PPractick

The problem

A utility company models its power lines as an undirected graph and needs to know whether the network contains any loop, because a loop means redundant paths that affect protection settings. Run BFS from every unvisited vertex, remembering which vertex discovered each vertex (its BFS parent). If an edge leads to an already visited vertex that isn't the parent, a second path to that vertex exists, so there's a cycle.

Example: 5 vertices, edges 0-1, 1-2, 2-3, 3-4, 4-1 → true (cycle 1-2-3-4).

Function signature

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

Test cases

Input (V, edges)	Output	Explanation
(5, [[0,1],[1,2],[2,3],[3,4],[4,1]])	true	1-2-3-4-1
(3, [[0,1],[1,2],[2,0]])	true	A triangle
(4, [[1,2],[2,3]])	false	A path, and vertex 0 is isolated
(4, [[0,1],[2,3]])	false	A forest of two edges
(1, [])	false

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

How interviewers phrase it

• "Given an undirected graph with V vertices, check whether it contains any cycle, using BFS" (GeeksforGeeks "Detect cycle in an undirected graph").

Clarifying questions to ask

1. Can the graph be disconnected? (Yes, so start BFS from every unvisited vertex.)
2. Are there self-loops or parallel edges? (Assume a simple graph. A self-loop is a cycle by itself, and parallel edges need edge IDs rather than parent vertices.)
3. Adjacency list or edge list? (An adjacency list.)

Follow-ups to expect

1. "Why exclude the parent?"
2. "Why does any other visited neighbour mean a cycle?"
3. "DFS version?"
4. "Other methods?"
5. "Complexity?"

Related questions

• Detect a cycle in an undirected graph Hard
• Word ladder I Hard
• Word ladder II Hard
• Cycle Detection in Directed Graph (DFS) Hard
• Topological sort or Kahn's algorithm Hard
• Detect a cycle in a directed graph Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in