Input: n = 5, edges = [[0,3], [1,3], [3,5], [5,4], [4,3]]
Output: true
Explanation: The graph has a cycle: 3 → 5 → 4 → 3. Starting from node 3, we can traverse to node 5, then to node 4, and finally back to node 3, forming a directed cycle. Nodes 0 and 1 both point to node 3, but they don't affect the cycle detection.
Input: n =4, edges =[[0,1],[1,2],[2,3]]Output: falseExplanation: This is a simple directed path 0→1→2→3with no cycles. Each node is visited at most once, and there are no back edges.
Input: n = 2, edges = [[0,1], [1,1]]
Output: true
Explanation: Self-loop cycle at node 1. Node 1 has an edge pointing to itself, which creates a cycle.
DFS for a connected graph produces a tree. For a disconnected graph, Get the DFS forest as output.
Graph contains cycle if there are any back edges. We have already seen Types of Edges in Graph.
There are two types of back edges as seen in the example above (marked in red)
Edge from a vertex to itself. Self loop. (4-4)
Edge from any descendent back to vertex.
To detect a back edge, keep track of vertices currently in the recursion stackrecursionStk[] of function for DFS traversal. If a vertex is reached that is already in the recursion stack, then there is a cycle in the tree. The edge that connects the current vertex to the vertex in the recursion stack is a back edge. Use recursionStk[] array to keep track of vertices in the recursion stack.
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)
visited = [False] * n
recursion_stack = [False] * n
# Check each componentfor i in range(n):
ifnot visited[i]:
if self._dfs(i, adj, visited, recursion_stack):
returnTruereturnFalsedef_dfs(self, u: int, adj: List[List[int]], visited: List[bool], recursion_stack: List[bool]) -> bool:
# Mark current node as visited and add to recursion stack visited[u] =True recursion_stack[u] =True# Visit all adjacent verticesfor v in adj[u]:
ifnot visited[v]:
# If not visited, recurseif self._dfs(v, adj, visited, recursion_stack):
returnTrueelif recursion_stack[v]:
# If visited and in recursion stack, cycle foundreturnTrue# Remove from recursion stack before backtracking recursion_stack[u] =FalsereturnFalse
⏰ 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 once
🧺 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
Method 2 - BFS (Kahn’s Algorithm for Topological Sort)#
While DFS is the natural approach for cycle detection in directed graphs, we can also use BFS through Kahn’s Algorithm for topological sorting. The key insight is that a directed graph has a cycle if and only if it cannot be topologically sorted.
classSolution {
public:bool hasCycle(int n, vector<vector<int>>& edges) {
// Build adjacency list and calculate in-degrees
vector<vector<int>> adj(n);
vector<int> inDegree(n, 0);
for (auto& edge : edges) {
adj[edge[0]].push_back(edge[1]);
inDegree[edge[1]]++;
}
// Add all vertices with in-degree 0 to queue
queue<int> q;
for (int i =0; i < n; i++) {
if (inDegree[i] ==0) {
q.push(i);
}
}
int processedCount =0;
// Process vertices using Kahn's algorithm
while (!q.empty()) {
int u = q.front();
q.pop();
processedCount++;
// Reduce in-degree of all neighbors
for (int v : adj[u]) {
inDegree[v]--;
if (inDegree[v] ==0) {
q.push(v);
}
}
}
// If we couldn't process all vertices, cycle exists
return processedCount != n;
}
};
classSolution {
publicbooleanhasCycle(int n, int[][] edges) {
// Build adjacency list and calculate in-degrees List<List<Integer>> adj =new ArrayList<>();
int[] inDegree =newint[n];
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
inDegree[edge[1]]++;
}
// Add all vertices with in-degree 0 to queue Queue<Integer> queue =new LinkedList<>();
for (int i = 0; i < n; i++) {
if (inDegree[i]== 0) {
queue.offer(i);
}
}
int processedCount = 0;
// Process vertices using Kahn's algorithmwhile (!queue.isEmpty()) {
int u = queue.poll();
processedCount++;
// Reduce in-degree of all neighborsfor (int v : adj.get(u)) {
inDegree[v]--;
if (inDegree[v]== 0) {
queue.offer(v);
}
}
}
// If we couldn't process all vertices, cycle existsreturn processedCount != n;
}
}
from collections import deque
from typing import List
classSolution:
defhas_cycle(self, n: int, edges: List[List[int]]) -> bool:
# Build adjacency list and calculate in-degrees adj = [[] for _ in range(n)]
in_degree = [0] * n
for u, v in edges:
adj[u].append(v)
in_degree[v] +=1# Add all vertices with in-degree 0 to queue queue = deque()
for i in range(n):
if in_degree[i] ==0:
queue.append(i)
processed_count =0# Process vertices using Kahn's algorithmwhile queue:
u = queue.popleft()
processed_count +=1# Reduce in-degree of all neighborsfor v in adj[u]:
in_degree[v] -=1if in_degree[v] ==0:
queue.append(v)
# If we couldn't process all vertices, cycle existsreturn processed_count != n
Union Find is not suitable for directed graph cycle detection and should be avoided. The fundamental issue is that Union Find treats all relationships as bidirectional, completely ignoring the directed nature of edges. For a directed edge A → B, Union Find treats it as A ↔ B, which fundamentally misunderstands directed graph semantics.
This leads to both false positives and false negatives. For example, consider edges [A→C, B→C] - Union Find would union A and C, then try to union B and C, incorrectly detecting a “cycle” when there isn’t one in the directed graph. The core concept of Union Find is about connecting components bidirectionally, which is fundamentally different from directed graph traversal and cycle detection.