Course Schedule II

01 · Question

Return the ordering of courses you should take to finish all courses. If impossible, return an empty array.

02 · Analysis

For [course, prerequisite], add prerequisite -> course. Queue every zero-indegree course, remove it, and decrement all dependent indegrees. The queue contains exactly the courses whose prerequisites are finished. A result shorter than numCourses proves a cycle somewhere in the graph. Time O(V+E), auxiliary space O(V), plus O(V+E) graph storage. Any valid order is acceptable.

03 · Solution

Reference solution

1from collections import deque
2
3def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
4    graph = [[] for _ in range(numCourses)]
5    indeg = [0] * numCourses
6    for a, b in prerequisites:
7        graph[b].append(a)
8        indeg[a] += 1
9
10    q = deque([i for i in range(numCourses) if indeg[i] == 0])
11    order = []
12
13    while q:
14        cur = q.popleft()
15        order.append(cur)
16        for nxt in graph[cur]:
17            indeg[nxt] -= 1
18            if indeg[nxt] == 0:
19                q.append(nxt)
20
21    return order if len(order) == numCourses else []

Find All Possible Recipes from Given Supplies