Graphs/Practice/Course Schedule
Course Schedule - Topological Sort Explained
Count how many prerequisites each course has, and build the reverse edges. Start with courses that have zero prerequisites - they are takeable now. "Taking" one decrements the count of every course that depended on it; those that hit zero join the ready list.
Why it works
This is Kahn’s topological sort: it processes courses in a valid order, and a cycle is exactly a set of courses whose counts never reach zero. If the ready queue empties before all courses are processed, a cycle blocked them - return false. O(V + E) total.
The problem
There are n courses labeled 0 to n-1. Given prerequisites pairs [a,b] meaning you must take b before a, return true if you can finish all courses (i.e., no cycle exists).
Hints
- This is a cycle detection problem in a directed graph.
- Use Kahn's algorithm: compute in-degrees, BFS from zero-indegree nodes.
- If the topological order includes all n nodes, no cycle exists.
- Alternatively, DFS with coloring: white (unvisited), gray (in-progress), black (done).
Test cases
| Input | Expected |
|---|---|
can_finish(2, [[1,0]]) | True |
can_finish(2, [[1,0],[0,1]]) | False |
Reference starter code
from collections import deque
def can_finish(num_courses, prerequisites):
# Topological sort / cycle detection
pass
print(can_finish(2, [[1, 0]])) # True
print(can_finish(2, [[1, 0], [0, 1]])) # False
print(can_finish(4, [[1,0],[2,0],[3,1],[3,2]])) # True
More challenges in this topic
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.