0210. 课程表 II【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - BFS 拓扑排序

1. 📝 题目描述

• leetcode

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

• 例如，想要学习课程 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 <= ai, bi < numCourses
• ai != bi
• 所有[ai, bi] 互不相同

2. 🎯 s.1 - BFS 拓扑排序

c

int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize) {
    int* inDegree = (int*)calloc(numCourses, sizeof(int));
    int** graph = (int**)malloc(sizeof(int*) * numCourses);
    int* graphSize = (int*)calloc(numCourses, sizeof(int));
    int* graphCap = (int*)malloc(sizeof(int) * numCourses);
    for (int i = 0; i < numCourses; i++) {
        graphCap[i] = 4;
        graph[i] = (int*)malloc(sizeof(int) * 4);
    }
    for (int i = 0; i < prerequisitesSize; i++) {
        int a = prerequisites[i][0], b = prerequisites[i][1];
        if (graphSize[b] == graphCap[b]) {
            graphCap[b] *= 2;
            graph[b] = realloc(graph[b], sizeof(int) * graphCap[b]);
        }
        graph[b][graphSize[b]++] = a;
        inDegree[a]++;
    }
    int* queue = (int*)malloc(sizeof(int) * numCourses);
    int front = 0, rear = 0;
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) queue[rear++] = i;
    }
    int* order = (int*)malloc(sizeof(int) * numCourses);
    *returnSize = 0;
    while (front < rear) {
        int cur = queue[front++];
        order[(*returnSize)++] = cur;
        for (int i = 0; i < graphSize[cur]; i++) {
            int next = graph[cur][i];
            if (--inDegree[next] == 0) queue[rear++] = next;
        }
    }
    for (int i = 0; i < numCourses; i++) free(graph[i]);
    free(graph); free(graphSize); free(graphCap); free(inDegree); free(queue);
    if (*returnSize != numCourses) { *returnSize = 0; }
    return order;
}

js

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
  const inDegree = new Array(numCourses).fill(0)
  const graph = Array.from({ length: numCourses }, () => [])
  for (const [a, b] of prerequisites) {
    graph[b].push(a)
    inDegree[a]++
  }
  const queue = []
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i)
  }
  const order = []
  while (queue.length) {
    const cur = queue.shift()
    order.push(cur)
    for (const next of graph[cur]) {
      inDegree[next]--
      if (inDegree[next] === 0) queue.push(next)
    }
  }
  return order.length === numCourses ? order : []
}

py

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        in_degree = [0] * numCourses
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)
            in_degree[a] += 1
        queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
        order = []
        while queue:
            cur = queue.popleft()
            order.append(cur)
            for nxt in graph[cur]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
        return order if len(order) == numCourses else []

• 时间复杂度：$O(V+E)$，其中 $V$ 是课程数，$E$ 是先修关系数
• 空间复杂度：$O(V+E)$，邻接表和入度数组

算法思路：

• 与 0207 相同的 BFS 拓扑排序，额外记录遍历顺序作为结果
• 若存在环则返回空数组