Detect a cycle — directed and undirected
Problem
Return true if the graph contains a cycle. Handle both cases: an undirected graph (a visited neighbour that is not your parent means a cycle) and a directed graph (reaching a node still on the current DFS path means a cycle).
Example 1
Input: directed: 0→1, 1→2, 2→0 Output: true
Example 2
Input: undirected: 0–1, 1–2 Output: false
Also asked as: Detect Cycle in Directed Graph using BFS/DFS Algo · Detect Cycle in UnDirected Graph using BFS/DFS Algo · Find whether it is possible to finish all tasks or not from given dependencies
Test cases
Case 1
Input: [[1],[2],[0]] Expected: true
Case 2
Input: [[1,2],[2],[]] Expected: false
Case 3
Input: [[0]] Expected: true
Case 4
Input: [[],[]] Expected: false
View solutionHide solution2 approaches
1. Directed — DFS with 3 colours (or Kahn count)
Time O(V + E)Space O(V)
grey = on the current DFS path. An edge to a grey node is a back-edge ⇒ cycle. "Can finish all tasks" is exactly "the dependency DAG has no cycle".
function hasCycleDirected(adj) { const state = new Array(adj.length).fill(0); // 0 unseen, 1 grey, 2 done const dfs = (u) => { state[u] = 1; for (const v of adj[u]) { if (state[v] === 1) return true; if (state[v] === 0 && dfs(v)) return true; } state[u] = 2; return false; }; for (let i = 0; i < adj.length; i++) if (state[i] === 0 && dfs(i)) return true; return false;}2. Undirected — DFS tracking the parent (or Union-Find)
Time O(V + E)Space O(V)
A visited neighbour that is not the node you came from means a cycle. Alternatively, an edge whose endpoints are already in the same DSU set forms a cycle.
function hasCycleUndirected(adj) { const seen = new Array(adj.length).fill(false); const dfs = (u, parent) => { seen[u] = true; for (const v of adj[u]) { if (!seen[v]) { if (dfs(v, u)) return true; } else if (v !== parent) return true; } return false; }; for (let i = 0; i < adj.length; i++) if (!seen[i] && dfs(i, -1)) return true; return false;}