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