The problem
There are numCourses courses, numbered from 0. Each pair [a, b] in prerequisites means course b must be taken before course a.
Return true if it is possible to take every course.
Examples
- Input
numCourses = 2, prerequisites = [[1, 0]]
- Output
true
- Input
numCourses = 2, prerequisites = [[1, 0], [0, 1]]
- Output
false
Constraints
- 1 ≤ numCourses ≤ 2000
- 0 ≤ prerequisites.length ≤ 5000
- No pair appears twice.
The idea
Draw each prerequisite as an arrow from b to a: a directed graph. The courses can all be taken unless the arrows form a cycle — a course that, through a chain of prerequisites, needs itself.
Kahn’s algorithm finds out by doing it. Count, for each course, how many prerequisites it still waits for. Any course waiting for none can be taken; taking it lowers the count of every course that needed it, and some of those may reach zero in turn. If every course gets taken, there is no cycle. Courses on a cycle never reach zero.
- Time
- O(V + E) — V courses, E prerequisites
- Space
- O(V + E)
Solution · every language run against every case
class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # Kahn's algorithm: take any course with no unmet prerequisite, then update the rest. after = [[] for _ in range(numCourses)] # course -> the courses that need it need = [0] * numCourses # course -> how many prerequisites it still waits for for course, pre in prerequisites: after[pre].append(course) need[course] += 1 ready = deque(c for c in range(numCourses) if need[c] == 0) taken = 0 while ready: c = ready.popleft() taken += 1 for nxt in after[c]: need[nxt] -= 1 if need[nxt] == 0: ready.append(nxt) return taken == numCourses # any course never taken is on a cycle