Course Schedule
Detect whether a set of dependencies can be satisfied, using topological sort to find a cycle
Problem Statement
There are numCourses courses labelled 0 to numCourses - 1. You are given prerequisites, where [a, b] means you must take b before a.
Return true if you can finish every course.
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Why: take 0, then 1
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Why: 1 needs 0, and 0 needs 1 — neither can go firstIntuition
Read the second example again. It is impossible not because there are too many courses, but because the requirements point in a circle.
The key insight
Every course list is finishable unless it contains a cycle.
If there is no cycle, some course must have no prerequisites left — you take it, cross it off, and that frees others. Repeat, and the whole list clears.
So the question "can I finish everything?" is really the question "does this dependency graph contain a cycle?"
Modelling it
Draw an arrow from b to a when b must come before a. The pair [1, 0] means "0 before 1", so the arrow runs 0 → 1.
The counting trick
There is a neat way to detect the cycle without ever explicitly looking for one.
For each course, count how many prerequisites it still needs. That number is its in-degree — the number of arrows pointing at it.
Kahn's algorithm, in one sentence
Repeatedly take any course whose in-degree is 0, and reduce the in-degree of everything that depended on it.
If you manage to take all n courses, there was no cycle. If you get stuck with courses left over, every remaining course is waiting on another remaining course — which is exactly what a cycle looks like.
The elegance is that you never search for the cycle. You just count how many courses you finished.
The real-world version
You have a pile of tasks with sticky notes saying what must come first. You look for a task with no sticky notes, do it, and then peel that task's name off every other note.
Doing a task frees others. If you eventually clear the pile, fine. If you reach a point where every remaining task still has a note on it, the tasks are waiting on each other and nothing can start.
Approach
Build the graph and count in-degrees
For each pair [a, b], add an edge b → a and increment inDegree[a].
Build both in the same loop — they describe the same information from two directions.
Queue every course with in-degree 0
These need no prerequisites and can be taken immediately. If this queue starts empty and there is at least one course, there is already a cycle.
Take a course, and free its dependents
Pop from the queue and increment a taken counter. For every course that depended on it, decrement that course's in-degree.
A course reaching in-degree 0 joins the queue
Its last prerequisite has just been satisfied.
Compare taken against numCourses
Equal means every course was reachable — no cycle. Fewer means the leftovers form a cycle.
Watch it run
Solution
from collections import defaultdict, deque
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
"""Return True when the dependency graph has no cycle (Kahn's algorithm)."""
# dependents[b] lists every course that becomes available after b.
dependents: defaultdict[int, list[int]] = defaultdict(list)
in_degree = [0] * num_courses
for course, prereq in prerequisites:
dependents[prereq].append(course) # edge prereq -> course
in_degree[course] += 1
# Everything that can be taken right now.
queue = deque(c for c in range(num_courses) if in_degree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for dependent in dependents[course]:
in_degree[dependent] -= 1
# Enqueue exactly when the LAST prerequisite is satisfied.
if in_degree[dependent] == 0:
queue.append(dependent)
# Anything left over is stuck waiting on something equally stuck.
return taken == num_coursesGet the edge direction right
[a, b] means take b before a, so the arrow is b → a. It is easy to build it backwards.
The reversed graph often still returns true on valid inputs, so small tests pass — and then it fails on an asymmetric case. Write the direction down before you code, and check it against the first example.
Complexity Analysis
Time Complexity
O(V + E)
Space Complexity
O(V + E)
Where V is numCourses and E is the number of prerequisite pairs.
- Time — building the graph touches each edge once. In the main loop each course is dequeued at most once, and each edge is examined exactly once when its source is taken.
- Space — the adjacency list holds
Eentries, and the in-degree array plus the queue holdV.
Edge Cases
Related Problems
- Number of Islands — traversal on an implicit grid graph
- Find the Town Judge — in-degree and out-degree again, without traversal
- Binary Tree Level Order Traversal — the same queue-driven wave, on a tree
- Graphs — representations, and why cycles force a visited set