Beyond awesome | 越而胜己

This is probably the most classic application of topological sorting. First, use the prerequisite list to build an adjacency table; then just run topological sort. The complexity is the same as topological sort, which is $\O(m+n)$, where $m$ is the number of edges (prerequisites) and $n$ is the number of vertices (courses.)

from collections import deque

class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
if numCourses == 0:
return []
in_degree =  * numCourses
out_edges = [set() for _ in range(numCourses)]
for p in prerequisites:
in_degree[p] += 1
s = deque([k for k, v in enumerate(in_degree) if v == 0])
order = []
while s:
print(s)
u = s.popleft()
for v in out_edges[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
s.append(v)
order.append(u)
print(order)
if len(order) == numCourses:
return order
else:
return []

You’ve successfully subscribed to Skyward
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.