Description
Given prerequisite pairs [course, prerequisite], decide whether all numbered courses can be completed.
Solution
from collections import deque
def can_finish(numCourses, prerequisites):
edges = [[] for _ in range(numCourses)]
degree = [0]*numCourses
for course, prerequisite in prerequisites:
edges[prerequisite].append(course)
degree[course] += 1
queue = deque(i for i in range(numCourses) if degree[i] == 0)
done = 0
while queue:
node = queue.popleft()
done += 1
for child in edges[node]:
degree[child] -= 1
if degree[child] == 0:
queue.append(child)
return done == numCoursesExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[3,[[1,0],[2,1]]]- Output
true
The dependency chain has no cycle.
Example 2
- Input
[2,[[1,0],[0,1]]]- Output
false
Each course depends on the other.
Example 3
- Input
[1,[]]- Output
true
A course with no prerequisites is immediately available.
Approach
Use Kahn's algorithm: repeatedly remove zero-indegree courses and release their dependents.
Time & space
O(V + E) time; O(V + E) auxiliary space for V courses and E prerequisite pairs.