LC210. Course Schedule II
Link to problem: https://leetcode.com/problems/course-schedule-ii/
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.)
这大概是最经典的拓扑排序算法(topological sort)的应用了。先使用 prerequisites
建立邻接表,然后直接运行 topological sort 即可。复杂度与 topological sort 相同,即 $\O(m+n)$,$n$ 为顶点(课程)数量,$m$ 为边(顺序要求)数量。
from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
if numCourses == 0:
return []
in_degree = [0] * numCourses
out_edges = [set() for _ in range(numCourses)]
for p in prerequisites:
in_degree[p[0]] += 1
out_edges[p[1]].add(p[0])
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 []