题目描述

[EN | CN]

现在你总共有 n 门课需要选,记为 0 到 n-1

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

给定课程总量以及它们的先决条件,返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序,你只要返回一种就可以了。如果不可能完成所有课程,返回一个空数组。

示例 1:

1
2
3
输入: 2, [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1,你需要先完成课程 0。因此,正确的课程顺序为 [0,1] 。

示例 2:

1
2
3
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3,你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此,一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

说明:

  1. 输入的先决条件是由 表示的图形,而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

解法 1:拓扑排序

跟《LeetCode 207. 课程表 ⌨️》(本博客)基本一样,只是那道题不需要输出顺序。在那道题的代码上面略作修改即可。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        src_to_dsts = {src:set() for src in range(numCourses)}
        dst_to_indegree = {dst:0 for dst in range(numCourses)}
        for src, dst in prerequisites:
            src_to_dsts[src].add(dst)
            dst_to_indegree[dst] += 1

        rets = []
        while True:
            dsts_without_src = {dst for dst, indegree in dst_to_indegree.items() if indegree == 0}
            if len(dsts_without_src) == 0:
                break
            for node in dsts_without_src:
                rets.append(node)
                for dst in src_to_dsts[node]:
                    dst_to_indegree[dst] -= 1
                dst_to_indegree.pop(node)

        if len(rets) == numCourses:
            return rets[::-1]
        else:
            return []
  • 执行用时:132 ms,在所有 Python3 提交中击败了 24.92% 的用户。
  • 内存消耗:14.8 MB,在所有 Python3 提交中击败了 27.08% 的用户。

解法二:DFS

同上一解法,也是跟《LeetCode 207. 课程表 ⌨️》里的方法一致,改一下细节就好了:

  • 在 DFS 每次深入到底的时候将该结点插入 ret,此时该结点没有依赖了。
  • 最终返回 ret

具体略。