越而胜己 / Beyond awesome

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 []