Beyond awesome | 越而胜己

Link to problem:

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
        s = deque([k for k, v in enumerate(in_degree) if v == 0])
        order = []
        while s:
            u = s.popleft()
            for v in out_edges[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
        if len(order) == numCourses:
            return order
            return []
You’ve successfully subscribed to Skyward
Welcome back! You’ve successfully signed in.
Great! You’ve successfully signed up.
Your link has expired
Success! Check your email for magic link to sign-in.