LeetCode 210. 课程表 II

题目描述
现在你总共有 numCourses 门课程需要选修，课程编号为 0 到 numCourses - 1。给定一个数组 prerequisites，其中 prerequisites[i] = [ai, bi]，表示想要学习课程 ai 就必须先完成课程 bi。请你返回一种合法的课程学习顺序，以便完成所有课程。如果有多个有效顺序，返回任意一个。如果无法完成所有课程（即存在循环依赖），则返回一个空数组。

例子

• 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
  输出：[0,1,2,3] 或 [0,2,1,3] 等（多种可能）
  解释：要学1需先学0，要学2需先学0，要学3需先学1和2。一种可行的顺序是0→1→2→3。
• 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
  输出：[]
  解释：要学1需先学0，要学0又需先学1，形成循环依赖，无法完成。

解题思路详解
这是一个拓扑排序问题。课程为图中的节点，前置条件 [ai, bi] 表示一条有向边 bi → ai（bi 指向 ai），即学完 bi 才能学 ai。我们需要找到一种节点排列顺序，使得每条有向边的起点在终点之前出现。如果图中存在环，则无法排序，返回空数组。

方法：Kahn 算法（BFS 拓扑排序）

1. 建图：用邻接表存储每个节点指向的后续节点，同时记录每个节点的入度（指向该节点的边数）。
2. 初始化队列：将所有入度为 0 的节点加入队列。
3. BFS 处理：从队列取出节点，加入结果列表，然后遍历该节点的所有邻居，将邻居的入度减 1。如果邻居的入度变为 0，则加入队列。
4. 检查结果：如果结果列表长度等于课程总数，则排序成功；否则说明有环，返回空数组。

具体步骤分解

步骤 1：数据结构准备
假设 numCourses = 4，prerequisites = [[1,0],[2,0],[3,1],[3,2]]。

• 创建邻接表 graph：大小为 numCourses 的列表，graph[i] 存储课程 i 的所有后续课程。
• 创建入度数组 indegree：大小为 numCourses，indegree[i] 表示课程 i 的入度。

步骤 2：遍历边，填充图与入度

• 对 [1,0]：学 1 前需学 0 → 边 0 → 1，graph[0].append(1)，indegree[1] += 1。
• 对 [2,0]：边 0 → 2，graph[0].append(2)，indegree[2] += 1。
• 对 [3,1]：边 1 → 3，graph[1].append(3)，indegree[3] += 1。
• 对 [3,2]：边 2 → 3，graph[2].append(3)，indegree[3] += 1。

现在：
graph = [[1,2], [3], [3], []]
indegree = [0, 1, 1, 2]（0 入度 0，1 入度 1，2 入度 1，3 入度 2）

步骤 3：初始化队列
遍历所有课程，入度为 0 的节点加入队列。当前只有课程 0 入度为 0。
queue = [0]，result = []。

步骤 4：BFS 过程

1. 弹出 0，result.append(0)。遍历 0 的邻居 [1,2]：

   • 对邻居 1：indegree[1] 从 1 减为 0，入队。
   • 对邻居 2：indegree[2] 从 1 减为 0，入队。
     现在队列为 [1,2]。

2. 弹出 1，result.append(1)。遍历邻居 [3]：

   • indegree[3] 从 2 减为 1，不为 0，不入队。
     现在队列为 [2]。

3. 弹出 2，result.append(2)。遍历邻居 [3]：

   • indegree[3] 从 1 减为 0，入队。
     现在队列为 [3]。

4. 弹出 3，result.append(3)。邻居为空，不操作。

步骤 5：检查结果
result = [0,1,2,3]，长度等于课程数 4，排序成功。

有环情况的例子
numCourses = 3，prerequisites = [[1,0],[2,1],[0,2]]。
建图后：graph = [[1], [2], [0]]，indegree = [1,1,1]。
初始时所有节点入度均为 1，队列为空。BFS 无法开始，最终 result 为空列表，但课程数为 3，返回空数组。

复杂度分析

• 时间复杂度：O(V + E)，V 为课程数，E 为前置条件数。
• 空间复杂度：O(V + E)，用于存储图和入度。

代码实现（Python 示例）

from collections import deque
from typing import List

def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    
    for a, b in prerequisites:
        graph[b].append(a)  # b -> a
        indegree[a] += 1
    
    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    
    return result if len(result) == numCourses else []

关键点总结

• 拓扑排序只适用于有向无环图（DAG）。
• 入度为 0 的节点是当前可安全学习的课程。
• 每学完一门课（取出节点），就“移除”它对后续课程的前置限制（邻居入度减 1）。
• 如果最终有课程未学（入度未减到 0），说明存在环。