Detect Cycle in Undirected Graph
Description
Given an undirected graph represented as an adjacency list with V vertices (numbered 0 to V-1) and E edges, determine whether the graph contains a cycle (also called a loop).
A cycle in an undirected graph is a path that starts at some vertex, follows a sequence of edges through distinct vertices, and returns to the starting vertex without reusing any edge.
The graph may consist of multiple disconnected components. If any component contains a cycle, the answer is true. Only if all components are cycle-free (i.e., each component is a tree) should you return false.
Return true if the graph contains at least one cycle, and false otherwise.
Examples
Example 1
Input: adj = [[1, 2], [0, 2], [0, 1, 3], [2]]
Output: true
Explanation: The graph has 4 vertices and 4 edges:
- Node 0 connects to 1, 2
- Node 1 connects to 0, 2
- Node 2 connects to 0, 1, 3
- Node 3 connects to 2
Nodes 0, 1, and 2 form a cycle: 0 → 1 → 2 → 0. We can start at node 0, travel to node 1, then to node 2, and return to node 0 without reusing any edge. Therefore the graph contains a cycle.
Example 2
Input: adj = [[1], [0, 2], [1, 3], [2]]
Output: false
Explanation: The graph has 4 vertices and 3 edges forming a straight path: 0 — 1 — 2 — 3. With 4 vertices and only 3 edges (exactly V-1), this is a tree. There is no way to start at any vertex and return to it without retracing an edge. No cycle exists.
Example 3
Input: adj = [[1], [0], [3], [2]]
Output: false
Explanation: The graph has two disconnected components: {0, 1} connected by one edge, and {2, 3} connected by one edge. Each component is a tree (2 vertices, 1 edge). Neither component has a cycle, so the answer is false. This shows the importance of checking all components.
Constraints
- 1 ≤ V, E ≤ 10^5
- 0 ≤ edges[i][0], edges[i][1] < V
- The graph is undirected (if u is in adj[v], then v is in adj[u])
- The graph may have multiple disconnected components
- No self-loops or parallel edges
Editorial
Brute Force
Intuition
The most direct way to detect a cycle is to test the definition: a cycle exists when there are two distinct paths between some pair of vertices.
Consider any edge connecting nodes u and v. If we temporarily remove that edge and find that u can still reach v through the remaining graph, then there must be at least two paths between u and v — the direct edge we removed, and the alternative path we just found. Together, these form a cycle.
Think of it like roads between cities. If you close one road between City A and City B, and you can still drive from A to B using other roads, then those roads together with the closed road form a loop. If closing the road completely disconnects A from B, then that road was the only connection — no loop.
So the brute force strategy is: for each edge in the graph, temporarily remove it, then run a BFS or DFS from one endpoint to check if the other endpoint is still reachable. If any edge passes this test, a cycle exists.
Step-by-Step Explanation
Let's trace through with adj = [[1, 2], [0, 2], [0, 1, 3], [2]] (nodes: 0, 1, 2, 3; edges: (0,1), (0,2), (1,2), (2,3)):
Step 1: Collect all unique edges: (0,1), (0,2), (1,2), (2,3). We will test each edge.
Step 2: Test edge (0,1): temporarily remove it. Remaining edges: (0,2), (1,2), (2,3).
Step 3: Run BFS from node 0 to see if node 1 is still reachable.
- Start at node 0, mark visited. Enqueue neighbors: only node 2 (edge 0-1 is removed).
Step 4: Dequeue node 2. Its neighbors (excluding the removed edge endpoints for edge 0-1): nodes 1 and 3. Node 1 is unvisited — enqueue it.
Step 5: Node 1 is now reachable from node 0 even without the direct edge! The path is 0 → 2 → 1.
Step 6: Since both the removed edge (0→1) and the alternative path (0→2→1) exist, they form a cycle: 0 → 1 → 2 → 0.
Step 7: Return true. A cycle was found on the very first edge test.
Brute Force — Remove Edge and Check Connectivity — Watch how removing an edge and running BFS reveals whether that edge is part of a cycle. If the endpoints remain connected, a cycle exists.
Algorithm
- Collect all unique edges from the adjacency list
- For each edge (u, v):
a. Temporarily "remove" this edge (skip it during traversal)
b. Run BFS from node u
c. If node v is reached during BFS, return true (cycle found)
d. Restore the edge - If no edge passes the test, return false (no cycle)
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
bool isCycle(vector<vector<int>>& adj) {
int V = adj.size();
// Collect all unique edges
vector<pair<int,int>> edges;
for (int u = 0; u < V; u++) {
for (int v : adj[u]) {
if (u < v) edges.push_back({u, v});
}
}
// For each edge, remove it and check connectivity
for (auto& [eu, ev] : edges) {
vector<bool> visited(V, false);
queue<int> q;
q.push(eu);
visited[eu] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
for (int nbr : adj[node]) {
// Skip the removed edge in both directions
if ((node == eu && nbr == ev) ||
(node == ev && nbr == eu))
continue;
if (!visited[nbr]) {
visited[nbr] = true;
q.push(nbr);
}
}
}
if (visited[ev]) return true;
}
return false;
}
};from collections import deque
class Solution:
def isCycle(self, adj):
V = len(adj)
# Collect all unique edges
edges = []
for u in range(V):
for v in adj[u]:
if u < v:
edges.append((u, v))
# For each edge, remove it and check connectivity
for eu, ev in edges:
visited = [False] * V
queue = deque([eu])
visited[eu] = True
while queue:
node = queue.popleft()
for nbr in adj[node]:
# Skip the removed edge
if (node == eu and nbr == ev) or \
(node == ev and nbr == eu):
continue
if not visited[nbr]:
visited[nbr] = True
queue.append(nbr)
if visited[ev]:
return True
return Falseimport java.util.*;
class Solution {
public boolean isCycle(ArrayList<ArrayList<Integer>> adj) {
int V = adj.size();
// Collect all unique edges
List<int[]> edges = new ArrayList<>();
for (int u = 0; u < V; u++) {
for (int v : adj.get(u)) {
if (u < v) edges.add(new int[]{u, v});
}
}
// For each edge, remove it and check connectivity
for (int[] edge : edges) {
int eu = edge[0], ev = edge[1];
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
queue.add(eu);
visited[eu] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
for (int nbr : adj.get(node)) {
if ((node == eu && nbr == ev) ||
(node == ev && nbr == eu))
continue;
if (!visited[nbr]) {
visited[nbr] = true;
queue.add(nbr);
}
}
}
if (visited[ev]) return true;
}
return false;
}
}Complexity Analysis
Time Complexity: O(E × (V + E))
For each of the E edges, we run a BFS/DFS traversal that visits up to V vertices and E edges. In the worst case (no cycle), we perform E complete traversals, giving O(E × (V + E)) total operations.
With V and E up to 10^5, this could mean 10^5 × 2×10^5 = 2×10^10 operations — far too slow for typical time limits.
Space Complexity: O(V + E)
The visited array requires O(V) space, and the BFS queue can hold up to O(V) nodes. The edge collection requires O(E) space. Total: O(V + E).
Why This Approach Is Not Efficient
The brute force approach runs a full graph traversal for every single edge, resulting in O(E × (V + E)) time. With V and E up to 10^5, this could mean up to 10^10 operations, which will exceed time limits on any online judge.
The core inefficiency is redundant exploration. We traverse the same portions of the graph over and over for different edge removals. Most of the information we discover in one BFS is thrown away and recomputed in the next.
Key insight: We do not need to test each edge individually. Instead, we can detect a cycle in a single traversal by using parent tracking. When performing DFS, we keep track of which node we came from (the parent). If we ever encounter a neighbor that is already visited and is NOT our parent, we have found a back edge — proof that a cycle exists.
This eliminates all redundant work: each node and edge is examined exactly once, reducing the time from O(E × (V+E)) to O(V + E).
Optimal Approach - DFS with Parent Tracking
Intuition
Imagine you are exploring a maze. You walk through corridors, always remembering which room you just came from (your parent). At each new room, you look at all exits. If an exit leads to a room you have already visited, and it is not the room you just came from, then you have found a loop in the maze — you can go one way and come back another way.
This is exactly how DFS with parent tracking works. As we traverse the graph using DFS, we mark each node as visited. For each neighbor of the current node:
- If the neighbor is unvisited: Continue DFS recursively, marking the current node as the neighbor's parent.
- If the neighbor is visited AND it is the parent: This is just the edge we came from — in an undirected graph, every edge appears in both directions. This is safe to ignore.
- If the neighbor is visited AND it is NOT the parent: We have found a back edge. This back edge, together with the tree path from the neighbor to the current node, forms a cycle.
The parent tracking is the critical detail that distinguishes a genuine cycle from the trivial back-and-forth along an undirected edge. Without tracking the parent, every undirected edge would falsely appear as a cycle.
Since the graph may be disconnected, we start a DFS from every unvisited node to ensure all components are checked.
Step-by-Step Explanation
Let's trace through with adj = [[1, 2], [0, 2], [0, 1, 3], [2]]:
Step 1: Initialize visited array: [false, false, false, false]. Start DFS from node 0 with parent = -1.
Step 2: Visit node 0. Mark visited[0] = true. Parent of 0 is -1 (no parent). Neighbors: [1, 2].
Step 3: Process neighbor 1 of node 0. Node 1 is not visited → recurse DFS(1, parent=0).
Step 4: Visit node 1. Mark visited[1] = true. Parent of 1 is 0. Neighbors: [0, 2].
Step 5: Process neighbor 0 of node 1. Node 0 is visited. Is 0 the parent of 1? Yes (parent = 0). This is just the edge we came from — safe to skip. No cycle here.
Step 6: Process neighbor 2 of node 1. Node 2 is not visited → recurse DFS(2, parent=1).
Step 7: Visit node 2. Mark visited[2] = true. Parent of 2 is 1. Neighbors: [0, 1, 3].
Step 8: Process neighbor 0 of node 2. Node 0 is visited. Is 0 the parent of 2? No! (parent = 1, not 0). Node 0 is reachable via a path that does NOT include the edge we just traversed. This is a back edge — CYCLE DETECTED!
Step 9: The cycle is: 0 → 1 → 2 → 0. The tree edges are 0→1 and 1→2, and the back edge is 2→0. Return true.
DFS with Parent Tracking — Detecting a Back Edge — Watch how DFS explores the graph while tracking each node's parent. When a visited neighbor is found that is not the parent, a back edge reveals a cycle.
Algorithm
- Create a visited array of size V, initialized to false
- For each node i from 0 to V-1:
- If node i is already visited, skip it
- Otherwise, start DFS from node i with parent = -1:
a. Mark the current node as visited
b. For each neighbor of the current node:- If the neighbor is not visited: recurse DFS with the current node as parent
- If the neighbor is visited AND it is NOT the parent: return true (cycle found via back edge)
- If the neighbor is visited AND it IS the parent: skip (just the edge we came from)
c. If no cycle found in this subtree, return false
- If all components are explored without finding a cycle, return false
Code
#include <vector>
using namespace std;
class Solution {
public:
bool isCycle(vector<vector<int>>& adj) {
int V = adj.size();
vector<bool> visited(V, false);
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (dfs(i, -1, adj, visited))
return true;
}
}
return false;
}
private:
bool dfs(int node, int parent,
vector<vector<int>>& adj,
vector<bool>& visited) {
visited[node] = true;
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
// Unvisited neighbor — explore deeper
if (dfs(neighbor, node, adj, visited))
return true;
} else if (neighbor != parent) {
// Visited and not parent — back edge found
return true;
}
}
return false;
}
};class Solution:
def isCycle(self, adj):
V = len(adj)
visited = [False] * V
def dfs(node, parent):
visited[node] = True
for neighbor in adj[node]:
if not visited[neighbor]:
# Unvisited neighbor — explore deeper
if dfs(neighbor, node):
return True
elif neighbor != parent:
# Visited and not parent — back edge found
return True
return False
for i in range(V):
if not visited[i]:
if dfs(i, -1):
return True
return Falseimport java.util.*;
class Solution {
public boolean isCycle(ArrayList<ArrayList<Integer>> adj) {
int V = adj.size();
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (dfs(i, -1, adj, visited))
return true;
}
}
return false;
}
private boolean dfs(int node, int parent,
ArrayList<ArrayList<Integer>> adj,
boolean[] visited) {
visited[node] = true;
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
// Unvisited neighbor — explore deeper
if (dfs(neighbor, node, adj, visited))
return true;
} else if (neighbor != parent) {
// Visited and not parent — back edge found
return true;
}
}
return false;
}
}Complexity Analysis
Time Complexity: O(V + E)
Each vertex is visited exactly once due to the visited array check. For each vertex, we iterate through its adjacency list, examining each edge. Since every edge appears twice in an undirected graph's adjacency list (once for each endpoint), the total work across all adjacency lists is O(2E) = O(E). The outer loop iterating over all vertices adds O(V). Combined total: O(V + E).
For the given constraints (V, E ≤ 10^5), this runs in at most a few hundred thousand operations — well within time limits.
Space Complexity: O(V)
The visited array requires O(V) space. The DFS recursion stack can go up to O(V) deep in the worst case (a graph shaped like a long chain). Total auxiliary space: O(V).
Note: If the recursion depth is a concern for very large V, the DFS can be converted to an iterative version using an explicit stack, maintaining the same O(V) space but avoiding stack overflow risks.