Course Schedule: Cycle Detection with DFS and Three Colors
Solve Course Schedule by detecting cycles in a directed graph with DFS and three visit states — intuition, JavaScript code, a worked trace, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Course Schedule looks like a scheduling puzzle, but strip away the story and it's one clean graph question: can you finish every course when some courses require others first? You can — as long as the prerequisites don't loop back on themselves. Course A needs B, B needs C, and C needs A is an impossible degree plan, and spotting that impossibility is exactly cycle detection in a directed graph.
The trick most people miss on the first try: a plain "have I visited this node?" flag isn't enough. You need to distinguish "I'm currently exploring this node" from "I finished exploring it and it was fine." That one distinction is the whole problem.
The problem
You're given numCourses courses labeled 0 to numCourses - 1, and a list prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, false otherwise.
Input: numCourses = 3, prerequisites = [[1, 0], [2, 1]]
Output: true // take 0, then 1, then 2 — no conflict
Input: numCourses = 2, prerequisites = [[0, 1], [1, 0]]
Output: false // 0 needs 1, and 1 needs 0 — impossibleRead [a, b] as a dependency edge: b unlocks a. The question "can all courses be finished?" is identical to "does a valid ordering exist?", which is identical to "is this dependency graph free of cycles?" A directed graph with no cycles is a DAG (directed acyclic graph), and a DAG always has at least one valid topological order.
The brute force baseline
The naive instinct is to simulate: repeatedly find a course with no unmet prerequisites, "take" it, remove it, and repeat until you either finish everything or get stuck. That's essentially Kahn's algorithm and it works — but the tempting-but-wrong baseline is trying to validate each course independently by walking its full dependency chain from scratch.
function canFinish(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
for (const [course, prereq] of prerequisites) {
adj[prereq].push(course);
}
// For every course, walk forward and see if we ever loop back to it.
function reachesSelf(start, curr, path) {
for (const next of adj[curr]) {
if (next === start) return true;
if (!path.has(next)) {
path.add(next);
if (reachesSelf(start, next, path)) return true;
}
}
return false;
}
for (let i = 0; i < numCourses; i++) {
if (reachesSelf(i, i, new Set([i]))) return false;
}
return true;
}This re-explores the same subgraphs once per starting node. With V courses it can run a full traversal V times, giving O(V · (V + E)) in the worst case — a fresh Set and a fresh walk for every course, with zero memory of work already done. On a long dependency chain that's a lot of repeated wandering.
The key insight: three states, not two
A single "visited" boolean can't tell you why a node was visited. Consider walking from course 0 into course 3, then later reaching course 3 again from a totally different branch. If 3 was already fully explored and found safe, re-reaching it is fine — no cycle. But if you reach a node that you're still in the middle of exploring, you've walked in a circle. Same "visited" flag, opposite meanings.
The fix is three visit states per node:
0 = unvisited never touched
1 = visiting currently on the active DFS path (in the call stack)
2 = visited fully explored, subtree proven cycle-freeA cycle exists exactly when DFS follows an edge into a node whose state is 1. That edge points back to an ancestor still on your current path — a back-edge — which means the node depends, transitively, on itself. Hitting a state-2 node instead is a shortcut: you already proved that region is clean, so you stop and return false (no cycle here) without re-exploring it. That memoization is what the brute force lacked.
The optimal solution
Build an adjacency list where adj[prereq] lists every course that prereq unlocks, then run DFS with the three-state visited array.
function canFinish(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
for (const [course, prereq] of prerequisites) {
adj[prereq].push(course);
}
// 0 = unvisited, 1 = visiting, 2 = visited
const visited = new Array(numCourses).fill(0);
function hasCycle(curr) {
if (visited[curr] === 1) return true; // back-edge → cycle
if (visited[curr] === 2) return false; // already cleared
visited[curr] = 1; // mark as visiting
for (const neighbor of adj[curr]) {
if (hasCycle(neighbor)) return true;
}
visited[curr] = 2; // mark as fully processed
return false;
}
for (let i = 0; i < numCourses; i++) {
if (visited[i] === 0) {
if (hasCycle(i)) return false;
}
}
return true;
}Three details carry the correctness. First, the outer loop starts DFS from every unvisited node — the graph can be disconnected, so one starting point may not reach every course. Second, visited[curr] = 1 goes before the neighbor loop and visited[curr] = 2 goes after, so a node is only in state 1 while it's genuinely on the stack. Third, the state-2 early return is what keeps this at linear time — each node's subtree is explored once and never again.
Walkthrough
Trace numCourses = 4, prerequisites = [[1, 0], [2, 1], [3, 2], [1, 3]] — a cycle hidden inside a longer chain. Building the adjacency list gives adj[0] = [1], adj[1] = [2], adj[2] = [3], adj[3] = [1]. DFS starts at course 0.
| Step | Call | curr | Edge followed | visited [0,1,2,3] | Call stack |
|---|---|---|---|---|---|
| 1 | hasCycle(0) | 0 | — | [1,0,0,0] | 0 |
| 2 | hasCycle(1) | 1 | 0 → 1 | [1,1,0,0] | 0, 1 |
| 3 | hasCycle(2) | 2 | 1 → 2 | [1,1,1,0] | 0, 1, 2 |
| 4 | hasCycle(3) | 3 | 2 → 3 | [1,1,1,1] | 0, 1, 2, 3 |
| 5 | hasCycle(1) | 1 | 3 → 1 | [1,1,1,1] | 0, 1, 2, 3 |
Step 5 is the payoff. Following edge 3 → 1, DFS calls hasCycle(1) and finds visited[1] === 1. Course 1 is still on the active path — it was marked visiting back in step 2 and never finished, because we're still deep inside its subtree. That's the back-edge: course 3 depends on 1, but 1 already (transitively) depends on 3. The function returns true up the whole stack, the outer loop sees hasCycle(0) returned true, and canFinish returns false. No course ever reaches state 2 because the cycle is caught before any branch fully unwinds.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (re-walk per node) | O(V · (V + E)) | O(V) | fresh traversal restarted from every course |
| DFS + three states | O(V + E) | O(V + E) | each node and edge examined once |
V is the number of courses and E the number of prerequisite pairs. Every node flips through states 0 → 1 → 2 exactly once, and every edge in the adjacency list is followed exactly once, giving O(V + E) time. Space is the adjacency list O(V + E), the visited array O(V), and recursion depth up to O(V) on a single long chain.
Common mistakes
- Using a plain visited/unvisited boolean. Two states can't tell "on the current path" from "done and safe." You'll either flag valid re-visits as cycles or miss real ones. The third state is mandatory.
- Forgetting to reset the state after the neighbor loop. If you only ever set state to
1and never2, revisiting a legitimately-finished node reports a false cycle.visited[curr] = 2after exploring is what makes cross-branch revisits safe. - Only starting DFS from node 0. Prerequisite graphs are often disconnected. Loop over all courses and launch DFS from any still in state
0, or you'll skip entire components. - Reversing the edge direction.
[a, b]meansbbeforea, so the edge runsb → a(adj[b].push(a)). Buildingadj[a].push(b)inverts every dependency and quietly breaks the answer. - Ignoring recursion depth. A chain of 10⁵ courses recurses 10⁵ deep and can overflow the call stack; the iterative Kahn's-algorithm variant sidesteps that.
Where this pattern shows up next
The three-state DFS traversal is a core graph tool that reappears the moment nodes and edges show up:
- Find if Path Exists in Graph — the same DFS skeleton, reduced to a plain reachability check.
- All Paths From Source to Target — DFS over a DAG where the acyclic guarantee lets you enumerate every route.
- Max Area of Island — flood-fill DFS on a grid, the undirected cousin of this traversal.
- Redundant Connection — cycle detection again, solved with union-find instead of DFS coloring.
You can also step through Course Schedule interactively to watch the visit states flip and the back-edge light up the moment a cycle closes.
FAQ
Why does Course Schedule need three visit states instead of two?
A two-state visited flag collapses two very different situations into one. When DFS reaches an already-seen node, "seen" could mean "I'm still exploring it right now" (a cycle) or "I finished it earlier and it was fine" (perfectly legal). State 1 (visiting) versus state 2 (visited) draws that line: a back-edge into a state-1 node proves a cycle, while a state-2 node is a safe, memoized shortcut you can skip. With only a boolean you either raise false alarms on valid revisits or miss genuine cycles.
Is Course Schedule the same as topological sort?
They answer the same underlying question. A valid course order is a topological ordering of the dependency graph, and such an ordering exists if and only if the graph is acyclic. Course Schedule just asks the yes/no version — does a valid order exist? — so you only need cycle detection, not the order itself. The follow-up problem Course Schedule II asks you to actually return the ordering, which is where you build the full topological sort (via this DFS's post-order, or via Kahn's algorithm).
What is the time complexity of the DFS solution?
O(V + E), where V is the number of courses and E is the number of prerequisite pairs. Each course moves through the three visit states exactly once, so it's explored a single time, and every edge in the adjacency list is traversed exactly once. Space is O(V + E) for the adjacency list plus O(V) for the visited array and the recursion stack, which can reach depth V on one long dependency chain.
Can I solve Course Schedule with BFS instead of DFS?
Yes — Kahn's algorithm is the BFS approach. You compute each course's in-degree (how many prerequisites it has), queue every course with in-degree 0, and repeatedly remove a course while decrementing its neighbors' in-degrees. If you manage to remove all numCourses courses, the graph is acyclic and you return true; if some courses never reach in-degree 0, they're trapped in a cycle. It runs in the same O(V + E) time and avoids deep recursion, which makes it the safer choice when the dependency chain could be very long.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.