Course Schedule（课程表）

题目 / Problem

中文： 共有 numCourses 门课程需要完成，课程编号从 0 到 numCourses - 1。

给定数组 prerequisites，其中 prerequisites[i] = [aᵢ, bᵢ] 表示：如果想学习课程 aᵢ，必须先完成课程 bᵢ。

例如，[0, 1] 表示必须先完成课程 1，才能学习课程 0。

如果能够完成所有课程，返回 true；否则返回 false。

English: There are numCourses courses to take, labeled from 0 to numCourses - 1.

You are given an array prerequisites, where prerequisites[i] = [aᵢ, bᵢ] means course bᵢ must be completed before course aᵢ can be taken.

Return true if all courses can be finished. Otherwise, return false.

图模型 / Graph Model

将每门课程看作一个节点。对于先修关系 [course, prerequisite]，建立一条有向边：
Treat each course as a vertex. For [course, prerequisite], create the directed edge:

prerequisite → course

这条边表示必须先完成 prerequisite，才能继续学习 course。
The edge means prerequisite must be completed before course.

问题就转化为：
The problem becomes:

判断这个有向图中是否存在环。
Determine whether the directed graph contains a cycle.

如果没有环，可以找到一种合法的拓扑顺序并完成所有课程。
If there is no cycle, a valid topological ordering exists and all courses can be completed.
如果存在环，环中的每门课程都在等待另一门课程，无法开始。
If a cycle exists, every course in the cycle waits for another course in the same cycle, so none can begin.

示例 / Examples

Example 1

Input:  numCourses = 2, prerequisites = [[1,0]]
Output: true

0 → 1

完成课程 0 后可以学习课程 1，所以存在合法顺序 [0,1]。
After completing course 0, course 1 can be taken, so [0,1] is a valid ordering.

Example 2

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false

0 → 1
↑   ↓
└───┘

课程 1 依赖课程 0，课程 0 又依赖课程 1，形成环，因此无法完成所有课程。
Course 1 depends on course 0, while course 0 depends on course 1. This cycle makes completion impossible.

约束 / Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= aᵢ, bᵢ < numCourses
所有先修关系都互不重复。
All prerequisite pairs are unique.

解题思路一：Kahn 拓扑排序 / Approach 1: Kahn's Topological Sort

对于每门课程，记录：
For every course, store:

graph[course]：完成该课程后可以解锁的后续课程。
graph[course]: courses unlocked after completing this course.
indegree[course]：该课程仍需要完成的先修课程数量。
indegree[course]: the number of prerequisites still required by this course.

算法步骤 / Algorithm Steps

根据 prerequisites 构建邻接表和入度数组。
Build the adjacency list and indegree array from prerequisites.
将所有入度为 0 的课程加入队列。这些课程没有未完成的先修要求，可以立即学习。
Enqueue every course whose indegree is 0; these courses can be taken immediately.
每次从队列中取出一门课程，视为完成它。
Dequeue a course and consider it completed.
遍历它解锁的所有后续课程，将这些课程的入度减 1。
Visit all courses it unlocks and decrement their indegrees.
如果某门后续课程的入度变为 0，将它加入队列。
If a course's indegree becomes 0, enqueue it.
最后检查已完成课程数量是否等于 numCourses。
Finally, check whether the number of completed courses equals numCourses.

如果图中存在环，环内节点的入度永远无法降为 0，所以最终处理数量会小于课程总数。
If the graph contains a cycle, nodes in that cycle can never reach indegree 0, so fewer than all courses are processed.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = new Array(numCourses).fill(0);

  for (const [course, prerequisite] of prerequisites) {
    graph[prerequisite].push(course);
    indegree[course]++;
  }

  const queue = [];
  let front = 0;

  for (let course = 0; course < numCourses; course++) {
    if (indegree[course] === 0) {
      queue.push(course);
    }
  }

  let completed = 0;

  while (front < queue.length) {
    const course = queue[front++];
    completed++;

    for (const nextCourse of graph[course]) {
      indegree[nextCourse]--;

      if (indegree[nextCourse] === 0) {
        queue.push(nextCourse);
      }
    }
  }

  return completed === numCourses;
}

这里使用 front 索引读取队列，避免调用 JavaScript 数组的 shift()。
An index named front reads from the queue instead of using JavaScript's shift().

执行过程 / Walkthrough

假设：
Suppose:

numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]

对应的图：
Corresponding graph:

    ┌→ 1 ─┐
0 ──┤     ├→ 3
    └→ 2 ─┘

初始入度：
Initial indegrees:

course:   0  1  2  3
indegree: 0  1  1  2

步骤 / Step	完成课程 / Completed	入度变化 / Indegree Changes	新加入队列 / Enqueued	`completed`
初始 / Start	—	—	`[0]`	0
1	0	`1: 1→0`, `2: 1→0`	`1, 2`	1
2	1	`3: 2→1`	—	2
3	2	`3: 1→0`	`3`	3
4	3	无 / None	—	4

最终 completed === numCourses === 4，因此返回 true。
Finally, completed === numCourses === 4, so return true.

环为什么会阻塞拓扑排序？ / Why Does a Cycle Block Topological Sorting?

对于 Example 2：
For Example 2:

0 → 1 → 0

初始入度为：
Initial indegrees:

course:   0  1
indegree: 1  1

没有任何入度为 0 的节点，队列从一开始就是空的，completed 保持为 0。因此返回 false。
No node has indegree 0, so the queue is empty from the start and completed remains 0. Therefore, return false.

复杂度 / Complexity

设课程数量为 V，先修关系数量为 E。
Let V be the number of courses and E the number of prerequisite relations.

时间复杂度：O(V + E)。每门课程最多入队一次，每条边处理一次。
Time: O(V + E), because every course is enqueued at most once and every edge is processed once.
空间复杂度：O(V + E)。邻接表保存所有边，入度数组和队列最多保存所有课程。
Space: O(V + E) for the adjacency list, indegree array, and queue.

解题思路二：DFS 三色标记 / Approach 2: DFS with Three States

也可以通过 DFS 检测有向图中的环。为每个课程记录三种状态：
A DFS can also detect cycles in the directed graph. Give every course one of three states:

状态 / State	含义 / Meaning
`0`	尚未访问 / Unvisited
`1`	正在当前递归路径中访问 / Visiting in the current recursion path
`2`	已完成访问，确认无环 / Fully processed and cycle-free

如果 DFS 沿一条边遇到状态为 1 的节点，说明回到了当前递归路径中的祖先节点，即发现了环。
If DFS follows an edge to a state-1 node, it has returned to an ancestor in the current recursion path, revealing a cycle.

function canFinishDFS(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const state = new Array(numCourses).fill(0);

  for (const [course, prerequisite] of prerequisites) {
    graph[prerequisite].push(course);
  }

  function hasCycle(course) {
    if (state[course] === 1) {
      return true;
    }

    if (state[course] === 2) {
      return false;
    }

    state[course] = 1;

    for (const nextCourse of graph[course]) {
      if (hasCycle(nextCourse)) {
        return true;
      }
    }

    state[course] = 2;
    return false;
  }

  for (let course = 0; course < numCourses; course++) {
    if (state[course] === 0 && hasCycle(course)) {
      return false;
    }
  }

  return true;
}

为什么需要状态 `2`？ / Why Is State `2` Needed?

状态 2 表示该节点以及它能到达的所有路径已经检查完毕，并确认没有环。其他 DFS 再次到达它时可以立即返回，避免重复遍历。
State 2 means the node and every path reachable from it have already been checked and are cycle-free. Later DFS calls can return immediately instead of repeating work.

DFS 复杂度 / DFS Complexity

时间复杂度 / Time: O(V + E)
空间复杂度 / Space: O(V + E)，包括邻接表、状态数组和最坏 O(V) 的递归调用栈。
This includes the adjacency list, state array, and a recursion stack of up to O(V).

BFS 与 DFS 对比 / BFS vs. DFS

方法 / Method	判断依据 / Criterion	时间 / Time	空间 / Space
Kahn BFS	能否处理全部节点 / Whether all vertices can be processed	`O(V + E)`	`O(V + E)`
DFS 三色标记	是否遇到当前路径中的节点 / Whether DFS revisits a visiting node	`O(V + E)`	`O(V + E)`

Kahn 算法可以自然生成拓扑顺序；DFS 更直接地表达“检测环”。本题只要求布尔值，两种方法都适用。
Kahn's algorithm naturally produces a topological order, while DFS directly expresses cycle detection. Either works for this boolean problem.

易错点 / Common Pitfalls

[course, prerequisite] 对应的边是 prerequisite → course，方向不能写反。
[course, prerequisite] creates the edge prerequisite → course; do not reverse it.
入度增加的是 course，不是 prerequisite。
Increment the indegree of course, not prerequisite.
没有先修要求的独立课程也必须计入完成数量。
Isolated courses with no prerequisites must still count as completed.
Kahn 算法最终要比较处理节点数量与 numCourses，不能只判断初始队列是否为空。
Kahn's algorithm must compare processed count with numCourses; checking only the initial queue is insufficient.
DFS 中状态 1 表示当前递归路径，遇到它才说明有环；状态 2 的节点可以安全复用。
In DFS, revisiting state 1 indicates a cycle, while state 2 is safe to reuse.
prerequisites 为空时，所有课程都可以完成，应返回 true。
If prerequisites is empty, all courses can be completed, so return true.

Course Schedule