课程表 II

难度: Medium

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [a_i, b_i] ，表示在选修课程 a_i 前必须先选修 b_i 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

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

示例 2：

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

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
所有[a_i, b_i] 互不相同

Submission

运行时间: 25 ms

内存: 17.2 MB

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        res = []
        course_graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for pair in prerequisites:
            course_graph[pair[1]].append(pair[0])
            indegree[pair[0]] += 1
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        while queue:
            cur = queue.popleft()
            res.append(cur)
            for next_course in course_graph[cur]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)
        return res if len(res) == numCourses else []

Explain

该题解使用了拓扑排序的思路。首先根据输入的先修课要求构建有向图（邻接表表示），并统计每个课程的入度。然后将所有入度为0的课程加入队列中。每次从队列取出一个入度为0的课程，将其加入结果列表，并更新它指向的后续课程的入度（将入度减1）。如果更新后有课程入度变为0，就将其加入队列。最后如果学完所有课程，返回结果列表；否则无法学完所有课程，返回空列表。

时间复杂度: O(V+E)

空间复杂度: O(V+E)

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        res = []
        # 构建有向图的邻接表表示
        course_graph = [[] for _ in range(numCourses)]
        # 存储每个课程的入度
        indegree = [0] * numCourses
        # 根据先修课要求构建图和统计入度
        for pair in prerequisites:
            course_graph[pair[1]].append(pair[0])
            indegree[pair[0]] += 1
        # 将所有入度为0的课程加入队列
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        while queue:
            # 取出一个入度为0的课程
            cur = queue.popleft()
            res.append(cur)
            # 更新后续课程的入度
            for next_course in course_graph[cur]:
                indegree[next_course] -= 1
                # 如果入度变为0，加入队列
                if indegree[next_course] == 0:
                    queue.append(next_course)
        # 如果学完所有课程，返回结果列表；否则返回空列表
        return res if len(res) == numCourses else []

Explore

在拓扑排序中，使用队列处理入度为0的课程实现了广度优先搜索（BFS），从而确保了按层级顺序处理课程。如果改用栈来代替队列，这将转变成深度优先搜索（DFS），可能导致结果列表中课程的顺序不同，但只要结果满足课程的先决条件，这样的顺序也是有效的。也可以使用优先队列等数据结构，通过控制出队顺序，允许更多的结果顺序灵活性。总结来说，使用不同的数据结构能够实现拓扑排序，但会影响结果中课程的顺序。

是的，可以通过检查结果列表的长度是否等于课程总数来判断是否所有课程都已被学习完成。如果结果列表包含所有课程，则说明没有循环依赖，所有课程都能够被安排学习；如果长度不足，说明存在循环依赖或其他问题导致某些课程无法学习，因此返回空列表表示无法完成所有课程的学习。

拓扑排序的实现过程中，如果队列最终为空但仍有课程的入度不为0，这表明图中存在环。在题解中，这通过检查结果列表的长度是否等于课程总数来间接判断。若不等，说明存在未被访问且入度未减至0的课程，通常这是由于这些课程在一个环中。因此，题解中通过最终的长度检查隐含地处理了环的检测。

是的，如果有多个课程同时入度为0，它们的处理顺序将影响最终的学习顺序。这是因为不同的处理顺序可能导致不同的课程先被加入到结果列表中。然而，这种不同的顺序仍然会满足所有的先修课程要求，因此都是有效的拓扑排序结果。