Log inSign up
mediumGeeksforGeeksNot Started

Detect Cycle in Undirected Graph

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given an undirected graph with V vertices and E edges represented by an adjacency list adj, determine whether the graph contains any cycle.

The graph vertices are numbered from 0 to V - 1. The graph may be disconnected, meaning it can contain multiple independent components.

---

### Examples

Example 1: ``text Input: V = 5, E = 5, adj = [[1], [0, 2, 4], [1, 3], [2, 4], [1, 3]] 0 --- 1 --- 2 | | 4 --- 3 Output: true Explanation: 1 -> 2 -> 3 -> 4 -> 1 forms a cycle.

Example 2: ``text Input: V = 4, E = 3, adj = [[1, 2], [0], [0, 3], [2]] 1 --- 0 --- 2 --- 3 Output: false Explanation: The graph is a tree (acyclic connected graph).

---

### Constraints - 1 <= V <= 10^5 - 0 <= E <= 10^5 - 0 <= adj[i][j] < V - Graph is undirected and may contain multiple components.

Constraints:

  • 1 <= V <= 105
  • 0 <= E <= 105
  • 0 <= adj[i][j] < V
  • Graph may be disconnected

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Differentiate undirected cycle detection (parent tracking) from directed cycle detection (recursion stack/in-degree).
  • Implement both BFS queue pairs (node, parent) and recursive DFS dfs(node, parent).
  • Formulate cycle detection using Disjoint Set Union (DSU).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Detect if an undirected graph has any loops or cycles
  • Check if an undirected graph is a valid tree
  • Redundant edge detection in a network

Algorithmic Decision Tree:

  • If undirected graph -> Track (curr, parent).
  • If visited[neighbor] == true && neighbor != parent -> Return true (cycle).
  • Always loop 0 to V-1 to catch disconnected components.

Connected Patterns:

Graph Valid TreeRedundant ConnectionDetect Cycle in Directed Graph (uses recursion stack array)

1. Iterative BFS with (Node, Parent) Queue

Intuition

Push (startNode, -1) into the queue and mark it visited. For every dequeued (u, parent), check its neighbors. If neighbor is unvisited, mark it visited and push (neighbor, u). If neighbor is already visited and neighbor != parent, a cycle is detected.

Algorithm

  1. Initialize visited array of size V to false.
  2. Loop i from 0 to V - 1:
  3. If !visited[i]:
  4. visited[i] = true.
  5. Queue q pushes (i, -1).
  6. While queue is not empty:
  7. Pop (u, parent) from q.
  8. For each neighbor v in adj[u]:
  9. If !visited[v]:
  10. visited[v] = true.
  11. q.push((v, u)).
  12. Else if v != parent:
  13. Return true (cycle found).
  14. Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 bool isCycle(int V, std::vector<std::vector<int>>& adj) {
8 std::vector<bool> visited(V, false);
9
10 for (int i = 0; i < V; ++i) {
11 if (!visited[i]) {
12 std::queue<std::pair<int, int>> q;
13 visited[i] = true;
14 q.push({i, -1});
15
16 while (!q.empty()) {
17 auto [u, parent] = q.front();
18 q.pop();
19
20 for (int v : adj[u]) {
21 if (!visited[v]) {
22 visited[v] = true;
23 q.push({v, u});
24 } else if (v != parent) {
25 return true; // Cycle detected
26 }
27 }
28 }
29 }
30 }
31 return false;
32 }
33};
34
35int main() {
36 Solution sol;
37 std::vector<std::vector<int>> adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}};
38 std::cout << "BFS Cycle: " << (sol.isCycle(5, adj) ? "true" : "false") << " (Expected: true)\n";
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

2. Disjoint Set Union (DSU / Union-Find)

Intuition

In an undirected graph, every edge (u, v) attempts to connect two components. If u and v already belong to the same connected component (find(u) == find(v)), adding edge (u, v) creates a cycle.

Algorithm

  1. Initialize DSU with V elements.
  2. Loop u from 0 to V - 1:
  3. For each neighbor v in adj[u]:
  4. If u < v (check each undirected edge once):
  5. If find(u) == find(v):
  6. Return true (cycle found).
  7. unite(u, v).
  8. Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class DSU {
5 std::vector<int> parent, rank;
6public:
7 DSU(int n) : parent(n), rank(n, 0) {
8 for (int i = 0; i < n; ++i) parent[i] = i;
9 }
10 int find(int i) {
11 if (parent[i] == i) return i;
12 return parent[i] = find(parent[i]);
13 }
14 bool unite(int i, int j) {
15 int rootI = find(i);
16 int rootJ = find(j);
17 if (rootI != rootJ) {
18 if (rank[rootI] < rank[rootJ]) std::swap(rootI, rootJ);
19 parent[rootJ] = rootI;
20 if (rank[rootI] == rank[rootJ]) rank[rootI]++;
21 return true;
22 }
23 return false; // Already in same set -> cycle
24 }
25};
26
27class Solution {
28public:
29 bool isCycle(int V, std::vector<std::vector<int>>& adj) {
30 DSU dsu(V);
31
32 for (int u = 0; u < V; ++u) {
33 for (int v : adj[u]) {
34 if (u < v) { // Consider each undirected edge once
35 if (!dsu.unite(u, v)) {
36 return true; // Cycle detected
37 }
38 }
39 }
40 }
41 return false;
42 }
43};
44
45int main() {
46 Solution sol;
47 std::vector<std::vector<int>> adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}};
48 std::cout << "DSU Cycle: " << (sol.isCycle(5, adj) ? "true" : "false") << " (Expected: true)\n";
49 return 0;
50}

Time & Space Complexity

  • Time complexity: O(V + E * alpha(V))
  • Space complexity: O(V)

3. Canonical Recursive DFS with Parent Tracking (Industry Benchmark)

Intuition

The canonical graph cycle detection pattern. A recursive function dfs(node, parent) marks the current node visited. For every neighbor, if unvisited, recurse dfs(neighbor, node). If already visited and neighbor != parent, a back-edge exists, confirming a cycle.

Algorithm

  1. Initialize boolean visited array of size V to false.
  2. Define dfs(u, parent):
  3. visited[u] = true.
  4. For each neighbor v in adj[u]:
  5. If !visited[v]:
  6. If dfs(v, u): return true.
  7. Else if v != parent:
  8. Return true (back-edge found).
  9. Return false.
  10. Loop i from 0 to V - 1:
  11. If !visited[i]:
  12. If dfs(i, -1): return true.
  13. Return false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 bool dfs(int u, int parent, const std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
6 visited[u] = true;
7
8 for (int v : adj[u]) {
9 if (!visited[v]) {
10 if (dfs(v, u, adj, visited)) return true;
11 } else if (v != parent) {
12 return true; // Back-edge implies cycle
13 }
14 }
15 return false;
16 }
17public:
18 bool isCycle(int V, std::vector<std::vector<int>>& adj) {
19 std::vector<bool> visited(V, false);
20
21 for (int i = 0; i < V; ++i) {
22 if (!visited[i]) {
23 if (dfs(i, -1, adj, visited)) return true;
24 }
25 }
26 return false;
27 }
28};
29
30int main() {
31 Solution sol;
32 std::vector<std::vector<int>> adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}};
33 std::cout << "Canonical DFS Cycle: " << (sol.isCycle(5, adj) ? "true" : "false") << " (Expected: true)\n";
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative BFS with (Node, Parent) QueueO(V + E)O(V)FIFO queue stores (u, parent) pairs across components.Queue memory footprint
2.Disjoint Set Union (DSU)O(V + E * alpha(V))O(V)Checks if edge endpoints share the same set root before unioning.Union-find operations
3.Canonical Recursive DFS with Parent TrackingOptimalO(V + E)O(V)Passes parent node through recursive stack; checks visited && v != parent.Recursion depth on linear path graphs

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Not passing the parent parameter, incorrectly declaring every single edge as a cycle.

Pitfall 2:

Only running DFS from vertex 0, missing cycles in disconnected components.

Pitfall 3:

Using directed graph cycle detection logic on an undirected graph.

Crucial Edge Cases to Validate:

  • Disconnected graph with a cycle in a secondary component — Outer loop iterates from 0 to V - 1, discovering and checking every isolated component.
  • Graph is a tree (V vertices, V - 1 edges, connected, acyclic) — All visited neighbors are parent nodes, returns false.
  • Graph has self-loops or multiple edges — For self-loop u->u, v == u != parent, immediately detects cycle.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the parent check immediately: 'Because undirected edges are bidirectional, we must ignore the edge back to our immediate caller.'
  2. Mention the outer loop for disconnected components right away.
  3. Note the equivalence: An undirected graph with V vertices and V - 1 edges without cycles is a Tree.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the parent node check (v != parent) mandatory when checking if an already-visited neighbor indicates a cycle in an undirected graph?

2.How does cycle detection in an undirected graph differ from a directed graph?

3.What is the time complexity of the canonical DFS cycle detection on an adjacency list?

Back to DSA Sheet