Detect a cycle — directed and undirected

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}