🔗 课程表

题目来源：207. 课程表 – 力扣（LeetCode）

---

📌 题目描述

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

某些课程有先修要求，以数组 prerequisites 给出，其中 prerequisites[i] = [aᵢ, bᵢ] 表示：

想要学习课程 aᵢ，必须先完成课程 bᵢ。

请你判断是否可能完成所有课程的学习。

• 如果可以，返回 true；
• 否则，返回 false。

---

✅ 示例解析

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：先学课程 0，再学课程 1，可行。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：课程 0 依赖课程 1，课程 1 又依赖课程 0 → 形成循环依赖，无法完成。

---

⚠️ 提示

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• 所有课程对互不相同
• 课程编号在 [0, numCourses) 范围内

---

💡 解法：拓扑排序（Kahn 算法）—— O(V + E) 时间，O(V + E) 空间

Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 入度数组：rd[i] 表示课程 i 的先修课程数量
        int[] inDegree = new int[numCourses];
        // 邻接表：list[i] 存储学完课程 i 后可解锁的课程
        List<List<Integer>> graph = new ArrayList<>();
        
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }

        // 构建图与入度
        for (int[] pre : prerequisites) {
            int course = pre[0];      // 要学的课
            int prerequisite = pre[1]; // 先修课
            graph.get(prerequisite).add(course);
            inDegree[course]++;
        }

        // 初始化队列：所有入度为 0 的课程（无先修要求）
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 拓扑排序
        while (!queue.isEmpty()) {
            int current = queue.poll();
            numCourses--; // 完成一门课程

            // 解锁后续课程
            for (int next : graph.get(current)) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 若所有课程都能完成，则无环；否则存在循环依赖
        return numCourses == 0;
    }
}

✅ 关键点：

• 将课程依赖关系建模为有向图；
• 使用 Kahn 算法进行拓扑排序；
• 若最终能处理完所有课程 → 无环 → 可完成；
• 若剩余课程 > 0 → 存在环 → 不可完成。

---

📊 复杂度分析

• 时间复杂度：O(V + E)
  • V = numCourses（顶点数）
  • E = prerequisites.length（边数）
  • 每个节点和每条边仅被访问一次。
• 空间复杂度：O(V + E)
  • 邻接表存储图结构；
  • 入度数组和队列最多存储 V 个元素。

---

🧩 解题思路

核心思想：检测有向图中是否存在环

课程安排问题 ⇨ 有向图拓扑排序问题 ⇨ 判环问题

• 每门课程是一个节点；
• 每个先修关系 [a, b] 是一条有向边 b → a；
• 如果图中存在环，则无法满足所有依赖 → 无法完成课程。

为什么用拓扑排序？

拓扑排序的定义是：对有向无环图（DAG）的线性排序，使得对于每条边 u → v，u 在排序中出现在 v 之前。

✅ 能完成拓扑排序 ⇨ 图无环 ⇨ 课程可完成
❌ 无法完成拓扑排序 ⇨ 图有环 ⇨ 课程不可完成

Kahn 算法流程

1. 计算每个节点的入度；
2. 将入度为 0 的节点入队（无依赖，可立即学习）；
3. 依次出队，移除其出边，更新邻居入度；
4. 若邻居入度变为 0，入队；
5. 重复直到队列为空；
6. 若处理的节点数 = 总节点数 → 无环。