课程表 II

难度: Medium

现在总共有 numCourses 门课需要选，记为 0 到 numCourses-1。

给定一个数组 prerequisites ，它的每一个元素 prerequisites[i] 表示两门课程之间的先修顺序。例如 prerequisites[i] = [a_i, b_i] 表示想要学习课程 a_i ，需要先完成课程 b_i 。

请根据给出的总课程数 numCourses 和表示先修顺序的 prerequisites 得出一个可行的修课序列。

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

示例 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,1,2,3] or [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 门课，直接修第一门课就可。

提示:

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
prerequisites 中不存在重复元素

注意：本题与主站 210 题相同：https://leetcode-cn.com/problems/course-schedule-ii/

Submission

运行时间: 27 ms

内存: 17.2 MB

from collections import deque  
  
class Solution:  
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:  
        # 初始化课程依赖关系图  
        graph = [[] for _ in range(numCourses)]  
        indegree = [0] * numCourses  
          
        # 构建图和入度数组  
        for course, prerequisite in prerequisites:  
            graph[prerequisite].append(course)  
            indegree[course] += 1  
          
        # 初始化队列并将入度为0的课程加入队列  
        queue = deque()  
        for i in range(numCourses):  
            if indegree[i] == 0:  
                queue.append(i)  
          
        # 拓扑排序  
        order = []  
        while queue:  
            cur = queue.popleft()  # 从队列左侧弹出一个元素  
            order.append(cur)      # 将该课程加入结果列表  
            for next_course in graph[cur]:  
                indegree[next_course] -= 1  
                if indegree[next_course] == 0:  
                    queue.append(next_course)  # 将入度减为0的课程加入队列  
          
        # 如果排序的课程数量等于总课程数，则返回排序结果，否则存在循环依赖，返回空列表  
        return order if len(order) == numCourses else []

Explain

这个题解使用了拓扑排序的方法来安排课程的学习顺序。首先构建一个图和一个入度数组，图用于表示每门课作为先决条件时，会影响哪些课程，入度数组记录每门课程所需的先决条件数量。初始化时，将所有入度为0的课程（即没有先决条件的课程）加入队列。然后进行拓扑排序，每次从队列中取出一个课程，将其加入排序结果中，并减少其影响的课程的入度。如果减少后某课程的入度变为0，则将其加入队列。在遍历完所有课程后，如果排序的课程数量等于总课程数，则返回排序结果，否则说明存在循环依赖，返回空数组。

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

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

from collections import deque  

class Solution:  
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:  
        # Initialize graph and indegree list
        graph = [[] for _ in range(numCourses)]  
        indegree = [0] * numCourses  
        
        # Construct the graph and indegree array
        for course, prerequisite in prerequisites:  
            graph[prerequisite].append(course)  
            indegree[course] += 1  
        
        # Initialize queue and add courses with zero indegree
        queue = deque()  
        for i in range(numCourses):  
            if indegree[i] == 0:  
                queue.append(i)  
        
        # Topological sort
        order = []  
        while queue:  
            cur = queue.popleft()  # Dequeue an element from the left side
            order.append(cur)      # Add this course to the result list
            for next_course in graph[cur]:  
                indegree[next_course] -= 1  
                if indegree[next_course] == 0:  
                    queue.append(next_course)  # Enqueue the course with zero indegree
        
        # Return the course order if all courses are sorted; otherwise, return an empty list due to cycle
        return order if len(order) == numCourses else []

Explore

在构建图和入度数组时，如果存在重复的先决条件关系 [ai, bi]，这意味着课程 bi 需要课程 ai 完成。因为我们是在遍历先决条件列表时直接更新图和入度数组，重复的 [ai, bi] 会导致 bi 的入度被重复增加。这会错误地表示 bi 有更多的先决条件要完成。因此，算法会错误地推迟将 bi 加入到可完成课程队列中，这可能会导致拓扑排序失败并错误地返回空数组，即使实际上不存在依赖循环。为了避免这种情况，我们应该在添加边和更新入度前检查是否已经添加过相同的先决条件。

在拓扑排序的过程中，当存在多个课程的入度为0时，选择下一个课程是基于队列的先进先出（FIFO）原则。具体地，先被检测到入度为0的课程会先被加入队列，并且将先从队列中被取出用于排序。这种选择方式确实会影响最终的课程顺序，因为不同的入队顺序会导致不同的课程被先处理。然而，所有可能的课程顺序都是有效的，因为它们都满足先决条件的约束。

是的，如果最终排序的课程数量不等于总课程数，这意味着图中存在环。在拓扑排序中，只有当一个课程的所有先决条件已被满足（即入度为0），该课程才会被加入到排序中。如果图中存在环，则至少有一门课程在环中，其入度永远不会变为0。因此，这些课程不会被加入到排序结果中，导致排序结果中的课程数量少于总课程数。算法通过检测最终排序结果中的课程数量与总课程数是否相等来准确地检测出环的存在。如果不相等，表明存在环。