LeetCode 207. 课程表-尧图网络科技

题目描述

这个学期需要选修numCourses门课程，课程编号为0到numCourses - 1。

数组prerequisites表示课程之间的先修关系，其中prerequisites[i] = [ai, bi]表示：如果要学习课程ai，必须先学习课程bi。

例如：

[0, 1]

表示想学习课程0，需要先完成课程1。

要求判断是否可以完成所有课程。如果可以，返回true；否则返回false。

初始思路

一开始想到的是把二维数组转成链表，然后判断链表里是否存在循环。

但这题不是普通链表问题。一个课程可能有多个后续课程，也可能被多个课程依赖，所以它本质上是一张有向图，不是一条链表。

如果课程之间存在环，就说明有些课程互相依赖，无法完成所有课程。

例如：

0 -> 1 1 -> 0

这就表示学习0之前要先学1，学习1之前又要先学0，形成了死循环。

解题思路

这题可以用 DFS 判断有向图中是否存在环。

先根据prerequisites建图：

g[p[1]].add(p[0]);

这里的方向是：

先修课 -> 后续课

也就是如果p = [a, b]，表示学a之前必须先学b，所以建边b -> a。

然后用三色标记记录每个课程的访问状态：

0：未访问。
1：正在访问。
2：已经访问完成。

DFS 过程中，如果遇到一个状态为1的节点，说明这个节点还在当前递归路径上，又被重新访问到了，所以存在环。

如果存在环，就无法完成所有课程，返回false。

为什么需要三色标记

这题不能只用一个简单的visited。

因为有向图判环时，需要区分两种状态：

这个点以前访问过，并且已经确认它后面的路径没有环。
这个点正在当前 DFS 路径中，还没有退出递归。

只有遇到“正在访问”的点，才说明形成了环。

也就是代码里的：

if (color[y] == 1) { return true; }

当一个节点的所有后续节点都 DFS 完成后，要把它标记成2：

color[x] = 2;

表示这个点已经检查完成，以后再遇到它就不用重复搜索。

易错点

1. 建图方向

prerequisites[i] = [ai, bi]的含义是：学ai之前要先学bi。

所以边的方向应该是：

bi -> ai

对应代码：

g[p[1]].add(p[0]);

2. DFS 结束后要标记为完成

如果一个点搜索完没有发现环，要把它从1改成2。

否则其他路径再次访问到它时，可能会误以为遇到了环。

3. 外层要遍历所有课程

图不一定是连通的。

有些课程可能和课程0完全不在一个连通块里，所以不能只从一个课程开始 DFS，而是要遍历所有课程：

for (int i = 0; i < numCourses; i++) { if (color[i] == 0 && dfs(i, g, color)) { return false; } }

代码实现

class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { List<Integer>[] g = new ArrayList[numCourses]; Arrays.setAll(g, i -> new ArrayList<>()); int[] color = new int[numCourses]; for (int[] p : prerequisites) { g[p[1]].add(p[0]); } for (int i = 0; i < numCourses; i++) { if (color[i] == 0 && dfs(i, g, color)) { return false; } } return true; } public boolean dfs(int x, List<Integer>[] g, int[] color) { color[x] = 1; for (int y : g[x]) { if (color[y] == 1 || color[y] == 0 && dfs(y, g, color)) { return true; } } color[x] = 2; return false; } }