0207. 课程表【中等】

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

1. 📝 题目描述

• leetcode

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则 必须 先学习课程 bi。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0，你需要先完成课程 1。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false。

---

示例 1：

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

解释：
总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。这是可能的。

示例 2：

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

解释：
总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

---

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

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

c

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) {
    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 count = 0;
    while (front < rear) {
        int cur = queue[front++];
        count++;
        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);
    return count == numCourses;
}

js

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = 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)
  }
  let count = 0
  while (queue.length) {
    const cur = queue.shift()
    count++
    for (const next of graph[cur]) {
      inDegree[next]--
      if (inDegree[next] === 0) queue.push(next)
    }
  }
  return count === numCourses
}

py

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        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)
        count = 0
        while queue:
            cur = queue.popleft()
            count += 1
            for nxt in graph[cur]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
        return count == numCourses

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

算法思路：

• 建立邻接表和入度数组，将入度为 0 的节点加入队列
• BFS 遍历，每次取出节点后将其邻居入度减 1，入度为 0 的加入队列
• 若最终处理的节点数等于课程总数，则无环