Course Schedule
You can finish all courses iff the prerequisite graph has no cycle.
Kahn's Algorithm, Step by Step
Problem
You are given a number of courses labeled from 0 through numCourses - 1 and prerequisite pairs. A pair [a, b] means course b must be completed before course a. Return true if every course can eventually be completed, or false if the prerequisites create an impossible cycle.
Examples
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
The Goal
Decide whether you can finish every course. A pair [a, b] means you must take b before a.
Draw each pair as an edge b → a. You can finish exactly when these edges have no cycle. On a cycle, every course waits on another one in the same loop.
For [[1,0],[2,0],[3,1],[3,2]], take 0, then 1 and 2, then 3.
Only a cycle blocks you
A course can need several others and unlock several others. The only way to get stuck is a loop, like 0 needing 1 while 1 needs 0.
Finishable means no cycle.
Key Idea: Take What Nothing Blocks
A course's in-degree counts the prerequisites it still needs. A course at 0 can be taken now.
Taking it removes its edges, so each course it unlocks drops by one, and any that reach 0 join the queue. If the queue runs dry with courses left, those courses sit on a cycle or behind one. Their counts never reach 0.
Queue every course with in-degree 0.
Only 0, here.
Kahn's Algorithm
from collections import deque
def can_finish(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return len(order) == num_coursesorder is a valid schedule whenever one exists. Depth-first search can answer too, by watching for an edge back to a course still on the current path.
| Approach | What it tracks | A cycle shows up as |
|---|---|---|
| Kahn's | In-degrees and a queue | Courses left over |
| DFS | Three states per course | An edge to a course on the current path |
Walkthrough
Run it on [[1,0],[2,0],[3,1],[3,2]]. Reading the pairs gives in-degrees 0, 1, 1 and 2 for courses 0 to 3, so the queue starts as [0].
Taking 0 drops courses 1 and 2 to 0, and both join the queue. Taking 1 drops 3 to 1, since it still needs 2. Taking 2 drops 3 to 0.
order ends as [0, 1, 2, 3], all four courses, so the answer is True.
Checkpoint · predict the next step
Step 8 of 22 on the stage: Take it: order = [0].
course on 0 · queue = [] · order = [0] · 0: in 0 · 1: in 1 · 2: in 1 · 3: in 2 · numCourses 4
Pitfalls
- Point each edge from the prerequisite to the course:
[1, 0]is0 → 1. Reversed edges still find cycles, butordercomes out backwards. - Count every course taken. A non-empty queue at the start proves nothing.
- In DFS, reaching a course you finished earlier isn't a cycle. Only an edge to a course still on the current path is.
- A course in no pair has in-degree 0 and is taken at the start.
DFS reaches a course it finished earlier, by a different path. Is that a cycle?
Complexity
Building the graph reads each pair once. Each course is queued and taken once, and each edge is removed once, when its prerequisite is taken. Time is O(V + E) for V courses and E pairs.
The graph stores every edge, and the in-degrees and queue hold one entry per course, so space is O(V + E).
Kahn's algorithm
- Build the graph and in-degreesEach pair once.O(V + E)
- Take each courseQueued once.O(V)
- Remove each edgeOnce, when its prerequisite is taken.O(E)
Linear in the courses and the pairs.
In short
Model courses as a directed graph of prerequisites. Run Kahn's algorithm: repeatedly remove nodes with in-degree zero; if you can remove all of them, there's a valid order, otherwise a cycle blocks completion. A DFS with a recursion-stack cycle check works too.
Common mistake
Conflating 'visited' with 'in the current DFS path' — cycle detection needs the on-stack state, not just visited.