207. 课程表-育师

207. 课程表

中等

提示

你这个学期必须选修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]中的所有课程对互不相同

📝 核心笔记：课程表 (拓扑排序 / DFS 找环)

1. 核心思想 (一句话总结)

“红绿灯机制：遇到‘黄灯’就是追尾（环），遇到‘红灯’就是安全。”我们需要区分三种状态，防止重复计算并精准定位“回边”。

0 (White/未访问)：处女地，没去过。
1 (Gray/正在访问)：当前递归栈中的节点（黄灯）。如果在递归中又遇到了 1，说明咬到了自己的尾巴 -> 有环！
2 (Black/已完成)：死胡同或已经确认安全的节点（红灯）。下次遇到直接跳过，不用再跑一遍。

2. 算法流程 (三步走)

建图 (Adjacency List)：把[课程, 前置]转化为前置 -> 课程的邻接表。
遍历所有节点：图可能不是连通的，所以外层要用for循环遍历每一个节点。
DFS (三色状态流转)：

- 进门：标记为1(正在经手)。
- 查邻居：

- - 邻居是1：报警！有环！
  - 邻居是0：递归进去查。
  - 邻居是2：安全的，无视。

- 出门：标记为2(封存归档)，表示从我出发的所有路都走通了且没环。

🔍 代码回忆清单 (带注释版)

✅ 举例：

假设prerequisites = [[1,0], [2,0], [3,1]]

循环过程：

p = [1, 0]→g[0].add(1)→g[0] = [1]
p = [2, 0]→g[0].add(2)→g[0] = [1, 2]
p = [3, 1]→g[1].add(3)→g[1] = [3]

最终邻接表：

g[0] = [1, 2] // 学完 0 可以学 1 或 2 g[1] = [3] // 学完 1 可以学 3 g[2] = [] // 学完 2 没有后续课程 g[3] = [] // 学完 3 没有后续课程

// 题目：LC 207. Course Schedule class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { // 1. 建图 (邻接表) //创建一个数组，每个元素是一个列表 List<Integer>[] g = new ArrayList[numCourses]; //：给每个位置初始化一个空列表 Arrays.setAll(g, i -> new ArrayList<>()); for (int[] p : prerequisites) { // p[1] 是先修课，p[0] 是后修课 // 边方向：先修 -> 后修 // 从先修课 p[1] 指向后修课 p[0] g[p[1]].add(p[0]); } // 2. 状态数组 (0:未访, 1:递归中, 2:已完成) int[] colors = new int[numCourses]; // 3. 处理非连通图 (孤岛也要查) for (int i = 0; i < numCourses; i++) { // 只有没访问过的才进 DFS // 如果 dfs 返回 true，说明"找到了环"，也就是"无法完成" -> return false if (colors[i] == 0 && dfs(i, g, colors)) { return false; } } return true; // 全跑完了没发现环 } // 返回值：true 表示“发现了环” private boolean dfs(int x, List<Integer>[] g, int[] colors) { colors[x] = 1; // 标记：我正在这条路径上 (入栈) // g[x] 是学完 x 后可以学的课程列表。 // y 就是其中一个后续课程。 for (int y : g[x]) { // 核心判断逻辑 if (colors[y] == 1) { return true; // 撞见自己人/祖先了 -> 环！ } if (colors[y] == 0 && dfs(y, g, colors)) { return true; // 递归子节点发现了环，层层上报 } // colors[y] == 2 的情况直接跳过 (剪枝) } colors[x] = 2; // 标记：我和我的子孙都检查过了，没问题 (出栈) return false; // 平安无事 } }