Description
Return an ordering of courses 0..numCourses-1 satisfying prerequisites [course, prerequisite]. Return an empty array when a cycle makes this impossible. Any valid order is acceptable.
Solution
from collections import deque
def find_order(num_courses, prerequisites):
edges = [[] for _ in range(num_courses)]
incoming = [0] * num_courses
for course, prerequisite in prerequisites:
edges[prerequisite].append(course)
incoming[course] += 1
ready = deque(i for i in range(num_courses) if incoming[i] == 0)
result = []
while ready:
course = ready.popleft()
result.append(course)
for next_course in edges[course]:
incoming[next_course] -= 1
if incoming[next_course] == 0:
ready.append(next_course)
return result if len(result) == num_courses else []Examples
Example 1
- Input
[2,[[1,0]]]- Output
[0,1]
Course 0 must precede course 1.
Example 2
- Input
[4,[[1,0],[2,0],[3,1],[3,2]]]- Output
[0,1,2,3]
1 and 2 may swap, but both follow 0 and precede 3.
Example 3
- Input
[2,[[1,0],[0,1]]]- Output
[]
The prerequisites form a cycle.
Approach
Build outgoing edges from prerequisites to courses and count incoming edges. Enqueue every zero-indegree course. Repeatedly emit one and decrement its dependents' indegrees; new zero-indegree courses become ready.
Time & space
O(V + E) time and auxiliary space, where V is the course count and E is the prerequisite count.