Course Schedule: cycle detection is the whole problem

The first time I hit this problem I started thinking about simulation — some kind of queue that replays the schedule. Took me a few minutes to realize the question has nothing to do with time. It is asking: is this directed graph acyclic? If yes, a valid ordering exists and you return true. If no, some chain of prerequisites loops back on itself and you return false. Everything else in the problem statement is flavor.

That reframe makes the solution space obvious. Cycle detection in a directed graph has exactly two standard approaches worth knowing: DFS with three-color marking, and Kahn's algorithm using BFS and in-degree counts. Both are O(V+E). The constraint says numCourses <= 2000 and prerequisites.length <= 5000, which means even a naive adjacency matrix would fit in memory — but an adjacency list is the natural representation, and both algorithms build it the same way.

What the constraints actually force

numCourses <= 2000. Vertices fit in an array indexed directly by course number. No hash map needed; graph[i] is i's neighbor list.

prerequisites.length <= 5000. That's the edge count. Combined with 2000 vertices, the graph is sparse — about 2.5 edges per vertex on average. Adjacency list is the right representation; adjacency matrix would waste 2000 × 2000 = 4M cells for 5000 edges.

All pairs are unique. You won't see duplicate edges, so you don't need to deduplicate during construction.

[a, b] means "take b before a" — edge direction is b -> a. I have gotten this backwards before. The way I remember it: b is the blocker, a is the course being blocked, so the arrow goes from blocker to blocked: b -> a.

DFS with three-color marking

The classical cycle-detection approach for directed graphs gives each node one of three states: unvisited (0), in the current DFS stack (1), fully processed (2). The cycle check is simple: if DFS reaches a node that is still in state 1 — still on the current path — you have found a back edge, which means a cycle.

Why three colors and not two? With two colors (visited / not visited), you cannot distinguish "I visited this node in a previous DFS call" from "I am currently in the middle of a path that goes through this node." The first case is safe. The second is a cycle. Two colors conflate them; three colors separate them.

Hand trace through Example 2: numCourses = 2, prerequisites = [[1,0],[0,1]].

Build the graph: edge 0->1 (from pair [1,0]) and edge 1->0 (from pair [0,1]).

graph[0] = [1]
graph[1] = [0]
states = [0, 0]

Call has_cycle(0):

• states[0] is 0, set to 1. states = [1, 0]
• Recurse into neighbor 1: call has_cycle(1)
  • states[1] is 0, set to 1. states = [1, 1]
  • Recurse into neighbor 0: call has_cycle(0)
    • states[0] is 1 -> cycle detected, return True
  • Propagate True up
• has_cycle(0) returns True, main loop returns False

Now the same trace for Example 1: numCourses = 2, prerequisites = [[1,0]].

graph[0] = [1]
graph[1] = []
states = [0, 0]

Call has_cycle(0):

• states[0] = 1. Recurse into 1.
  • states[1] = 1. No neighbors. Set states[1] = 2. Return False.
• states[0] = 2. Return False.

Call has_cycle(1): states[1] is already 2, return False immediately.

No cycle found, return True.

from typing import List
 
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for course, prereq in prerequisites:
            graph[prereq].append(course)
 
        # 0: unvisited, 1: visiting (on current stack), 2: fully processed
        states = [0] * numCourses
 
        def has_cycle(course: int) -> bool:
            if states[course] == 1:
                return True
            if states[course] == 2:
                return False
 
            states[course] = 1
            for neighbor in graph[course]:
                if has_cycle(neighbor):
                    return True
            states[course] = 2
            return False
 
        for course in range(numCourses):
            if states[course] == 0 and has_cycle(course):
                return False
 
        return True

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var graph = new List<int>[numCourses];
        for (int i = 0; i < numCourses; i++)
            graph[i] = new List<int>();
 
        foreach (var p in prerequisites)
            graph[p[1]].Add(p[0]);
 
        // 0: unvisited, 1: visiting, 2: fully processed
        var states = new int[numCourses];
 
        bool HasCycle(int course) {
            if (states[course] == 1) return true;
            if (states[course] == 2) return false;
 
            states[course] = 1;
            foreach (int neighbor in graph[course])
                if (HasCycle(neighbor)) return true;
            states[course] = 2;
            return false;
        }
 
        for (int course = 0; course < numCourses; course++)
            if (states[course] == 0 && HasCycle(course))
                return false;
 
        return true;
    }
}

Time: O(V+E) — every vertex is fully processed at most once (state 2 short-circuits all future visits), every edge is traversed at most once during that processing. Space: O(V+E) for the adjacency list plus O(V) for the states array and the recursion call stack — worst case O(V) stack depth for a linear chain of courses.

One real concern: Python's default recursion limit is 1000. With numCourses up to 2000 and a linear chain, you'd hit it. In production I'd either use sys.setrecursionlimit(3000) or convert to the iterative Kahn approach below. C# has a much deeper call stack and doesn't have this problem at these input sizes.

Kahn's algorithm: BFS topological sort

The second approach does not look for cycles directly. Instead it tries to build a valid topological ordering, and the check becomes: if you can schedule all courses, no cycle exists; if you get stuck with unprocessed courses, a cycle is trapping them.

The mechanism is in-degree. In-degree of a node is the number of edges pointing into it — the number of prerequisites for that course. A course with in-degree 0 has no prerequisites; it can be taken immediately. Take it, remove it from the graph (decrement the in-degree of every course that depended on it), and repeat. Any course that reaches in-degree 0 as a result joins the queue.

If the graph has a cycle, the nodes in that cycle will never reach in-degree 0 — each one still depends on at least one other node in the cycle. They will never enter the queue. The processed count will fall short of numCourses.

Full trace through a richer example: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]].

Edge list (b -> a from each pair):
  [1,0] -> 0 -> 1
  [2,0] -> 0 -> 2
  [3,1] -> 1 -> 3
  [3,2] -> 2 -> 3

graph[0] = [1, 2]
graph[1] = [3]
graph[2] = [3]
graph[3] = []

in_degree = [0, 1, 1, 2]

Initial queue: courses with in-degree 0 -> [0]. processed = 0.

Step 1: pop 0. processed = 1. Neighbors: 1, 2. Decrement in_degree[1] -> 0, in_degree[2] -> 0. Both join queue. Queue = [1, 2].

Step 2: pop 1. processed = 2. Neighbors: 3. Decrement in_degree[3] -> 1. Not zero yet. Queue = [2].

Step 3: pop 2. processed = 3. Neighbors: 3. Decrement in_degree[3] -> 0. Joins queue. Queue = [3].

Step 4: pop 3. processed = 4. No neighbors. Queue = [].

processed (4) == numCourses (4). Return True.

Now the cycle case: numCourses = 2, prerequisites = [[1,0],[0,1]].

graph[0] = [1], graph[1] = [0]
in_degree = [1, 1]

Queue starts empty — no node has in-degree 0. The while loop never executes. processed (0) != numCourses (2). Return False.

from collections import deque
from typing import List
 
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
 
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1
 
        queue = deque(c for c in range(numCourses) if in_degree[c] == 0)
        processed = 0
 
        while queue:
            course = queue.popleft()
            processed += 1
            for neighbor in graph[course]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
 
        return processed == numCourses

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var graph = new List<int>[numCourses];
        var inDegree = new int[numCourses];
 
        for (int i = 0; i < numCourses; i++)
            graph[i] = new List<int>();
 
        foreach (var p in prerequisites) {
            graph[p[1]].Add(p[0]);
            inDegree[p[0]]++;
        }
 
        var queue = new Queue<int>();
        for (int i = 0; i < numCourses; i++)
            if (inDegree[i] == 0)
                queue.Enqueue(i);
 
        int processed = 0;
        while (queue.Count > 0) {
            int course = queue.Dequeue();
            processed++;
            foreach (int neighbor in graph[course]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0)
                    queue.Enqueue(neighbor);
            }
        }
 
        return processed == numCourses;
    }
}

Time: O(V+E) — same reasoning as DFS. Every node enters the queue at most once; every edge is considered exactly once when its source node is dequeued. Space: O(V+E) for the graph, O(V) for in_degree and the queue.

Edge cases

No prerequisites. prerequisites = []. All in-degrees stay 0; every course enters the queue immediately. Kahn's processes all numCourses courses. DFS calls has_cycle for every course and immediately sets it to state 2 with no recursive calls. Both return True in O(V) time.

Self-loop. If somehow [a, a] appeared — a course that requires itself. The constraints say pairs are unique and 0 <= ai, bi < numCourses but nothing explicitly forbids a == b. With DFS: has_cycle(a) sets state to 1, then sees neighbor a which is in state 1 — returns True immediately. With Kahn's: in_degree[a] gets incremented but never decremented by anyone else, so it never reaches 0 and never gets processed. Both handle it correctly.

Disconnected graph. Multiple independent groups of courses with no prerequisites linking them. DFS handles this via the outer loop: it calls has_cycle for every course in 0..numCourses-1, which guarantees it visits every component even if they're disconnected. Kahn's handles it because every course with in-degree 0 starts in the queue regardless of which component it belongs to.

Linear chain. 0 -> 1 -> 2 -> ... -> n-1. No cycle. DFS descends the entire chain recursively — stack depth hits n-1. At numCourses = 2000, this is 1999 frames, which exceeds Python's default stack. Kahn's is fully iterative and handles this without issue.

All courses in one big cycle. 0 -> 1 -> 2 -> ... -> n-1 -> 0. Kahn's: no node ever reaches in-degree 0, queue is empty from the start, processed remains 0. DFS: visiting node 0, descends the entire chain, then hits node 0 again in state 1 — cycle detected.

Which one to ship

If the question is only "can you finish?" and you're comfortable with recursion, DFS is slightly more direct to reason about — you're literally following each prerequisite chain and looking for a back edge. The three-color logic is compact.

I would ship Kahn's. The reasoning is boring but real: it is iterative, so no recursion limit issue; it produces the topological order as a side effect (useful when Course Schedule II comes up in the next interview); and the termination condition is a single comparison rather than a propagated boolean through recursive calls. The code ends up being the same length. There is no reason to prefer DFS here unless you are in a language where recursion overhead matters more than clarity.

The pattern and where it shows up

This is the canonical topological sort / DAG validation problem. The mental model: any time you have a set of items with ordering constraints and you need to know whether a valid ordering exists, you're looking at this structure. Build the dependency graph, check for cycles.

The series builds on this directly. The next step is Course Schedule II (LeetCode 210), which is identical except you also return the actual ordering — Kahn's extends to this trivially by collecting the dequeued nodes. Graph Valid Tree (LeetCode 261) takes the same cycle detection idea into undirected graphs, where the check changes slightly — an undirected back edge is a cycle, but you have to be careful not to flag the edge you just came from. Alien Dictionary (LeetCode 269) uses the same topological sort but makes you construct the graph yourself from word-pair comparisons, which is the harder part of that problem. Find Eventual Safe States (LeetCode 802) inverts the question — instead of asking if the whole graph is cycle-free, it asks which individual nodes can never reach a cycle.

All four of those problems become straightforward once you can implement both solutions here without thinking about them.