LC210. 课程表II

LC210. 课程表II

题目描述

现在你总共有 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]

题目解析

解题思路

本题是经典的拓扑排序问题，将课程看作图中的节点，先修关系看作有向边 b → a（先修 b 才能学 a）。需要输出一种合法的课程学习顺序，若存在环则返回空数组。

采用 BFS 拓扑排序（Kahn 算法）：

• 用邻接表 h 存储每个节点的后继节点列表。
• 用 inDegreeList 记录每个节点的入度（即必须先修的课程数）。
• 初始将所有入度为 0 的节点（无先修要求的课程）加入队列，并加入答案。
• 每次从队列取出一个节点 cur，将其所有后继 nxt 的入度减 1；若减后入度为 0，则加入队列和答案。
• 最终若所有节点入度均为 0，说明无环，返回答案；否则返回空数组。

关键步骤

1. 建图与初始化：遍历 prerequisites，对每条 [a, b]，在 h[b] 中添加 a，并将 a 的入度加 1。 2. 初始队列：将所有入度为 0 的节点入队，同时加入答案列表。 3. BFS 过程：

   while 队列非空:
       cur = 出队
       for nxt in h[cur]:
           inDegreeList[nxt] -= 1
           if inDegreeList[nxt] == 0:
               入队 nxt
               答案追加 nxt

4. 环检测：遍历 inDegreeList，若存在非 0 值，说明有环，返回 []。

复杂度分析

• 时间复杂度：O(V + E)，其中 V = numCourses，E = prerequisites 长度。建图 O(E)，BFS 遍历所有节点和边 O(V + E)。
• 空间复杂度：O(V + E)，邻接表存储所有边，入度数组和队列各 O(V)。