Input: n = 6, edges = [[0,1], [1,2], [2,3], [3,4], [4,5], [5,2]]
Output: true
Explanation: The graph has a cycle: 2 -> 3 -> 4 -> 5 -> 2. Starting from node 2, we can traverse to node 3, then to node 4, then to node 5, and finally back to node 2, forming a cycle.
Input: n = 4, edges = [[0,1], [1,2], [2,3]]
Output: false
Explanation: This is a simple path 0-1-2-3 with no cycles. Each node is visited at most once, and there are no back edges.
Input: n = 3, edges = [[0,1], [1,2], [0,2]]
Output: true
Explanation: Triangle cycle: 0 -> 1 -> 2 -> 0. All three nodes are connected to each other forming a cycle.
DFS for a connected graph produces a tree. There is a cycle in a graph only if there is a back edge present in the graph. We have seen Types of Edges in Graph.
A back edge is an edge that is joining a node to itself (self-loop) or one of its ancestor in the tree produced by DFS.
To find the back edge to any of its ancestors keep a visited array and if there is a back edge to any visited node then there is a loop and return true.
Do DFS from every vertex (please read DFS for more details)
During DFS, for any current vertex ‘u’ (currently visiting vertex) if there is an adjacent vertex ‘v’ that is already visited and ‘v’ is not a direct parent of ‘u’ then there is a cycle in the graph
Why we ignore parent:
Let’s assume vertices u and v with edge between them: u—-v
When we do DFS from u and reach v, then from v we see u as adjacent and already visited
But this doesn’t indicate a cycle since u is the parent of v
That’s why we ignore the visited vertex if it is the parent of the current vertex
classSolution {
public:bool hasCycle(int n, vector<vector<int>>& edges) {
// Build adjacency list
vector<vector<int>> adj(n);
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
adj[edge[1]].push_back(edge[0]);
}
vector<bool> visited(n, false);
// Check each component
for (int i =0; i < n; i++) {
if (!visited[i]) {
if (dfs(i, -1, adj, visited)) {
return true;
}
}
}
return false;
}
private:bool dfs(int u, int parent, vector<vector<int>>& adj, vector<bool>& visited) {
visited[u] = true;
// Visit all adjacent vertices
for (int v : adj[u]) {
if (!visited[v]) {
// If not visited, recurse
if (dfs(v, u, adj, visited)) {
return true;
}
} elseif (v != parent) {
// If visited and not parent, cycle found
return true;
}
}
return false;
}
};
classSolution:
defhas_cycle(self, n: int, edges: List[List[int]]) -> bool:
# Build adjacency list adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
# Check each componentfor i in range(n):
ifnot visited[i]:
if self._dfs(i, -1, adj, visited):
returnTruereturnFalsedef_dfs(self, u: int, parent: int, adj: List[List[int]], visited: List[bool]) -> bool:
visited[u] =True# Visit all adjacent verticesfor v in adj[u]:
ifnot visited[v]:
# If not visited, recurseif self._dfs(v, u, adj, visited):
returnTrueelif v != parent:
# If visited and not parent, cycle foundreturnTruereturnFalse
⏰ Time complexity: O(V + E), where V is the number of vertices and E is the number of edges. We visit each vertex once and traverse each edge twice (once from each endpoint)
🧺 Space complexity: O(V + E), for the adjacency list representation and the recursion stack which can go up to O(V) in the worst case
Similar to DFS approach, we can use BFS to detect cycles in an undirected graph. The key insight is the same: if we encounter a visited vertex that is not the direct parent of the current vertex, then we have found a cycle.
from collections import deque
from typing import List
classSolution:
defhas_cycle(self, n: int, edges: List[List[int]]) -> bool:
# Build adjacency list adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
# Check each componentfor i in range(n):
ifnot visited[i]:
if self._bfs(i, adj, visited):
returnTruereturnFalsedef_bfs(self, start: int, adj: List[List[int]], visited: List[bool]) -> bool:
queue = deque([(start, -1)]) # (vertex, parent) visited[start] =Truewhile queue:
u, parent = queue.popleft()
# Visit all adjacent verticesfor v in adj[u]:
ifnot visited[v]:
# If not visited, add to queue visited[v] =True queue.append((v, u))
elif v != parent:
# If visited and not parent, cycle foundreturnTruereturnFalse
Union Find (also known as Disjoint Set Union) is another efficient approach to detect cycles in undirected graphs. The key insight is that if two vertices of an edge are already in the same connected component (same set), then adding this edge will create a cycle.
⏰ Time complexity: O(E × α(V)), where E is the number of edges, V is the number of vertices, and α is the inverse Ackermann function. With path compression and union by rank, α(V) is effectively constant for all practical purposes, making it nearly O(E)
🧺 Space complexity: O(V), for the parent and rank arrays in the Union Find data structure