【Leetcode 热题 100】207. 课程表

问题背景

你这个学期必须选修 $numCourses$ 门课程，记为 $0$ 到 $numCourses-1$。
在选修某些课程之前需要一些先修课程。 先修课程按数组 $prerequisites$ 给出，其中 $prerequisites[i]=[a_i,b_i]$，表示如果要学习课程 $a_i$ 则 必须 先学习课程 $b_i$。
例如，先修课程对 $[0,1]$ 表示：想要学习课程 $0$，你需要先完成课程 $1$。
请你判断是否可能完成所有课程的学习？如果可以，返回 $true$；否则，返回 $false$。

数据约束

• $1\le numCourses\le 2000$
• $0\le prerequisites.length\le 5000$
• $prerequisites[i].length=2$
• $0\le a_i,b_i<numCourses$
• $prerequisites[i]$ 中的所有课程对 互不相同

解题过程

判断是否是有向无环图的模板题，暴力的角度上看，深搜和广搜都能做，用图的入度来进行判断。
看了 灵神的题解 学到了三色标记法，进一步了解到这种方法能够解决拓扑排序的问题，决定目前的阶段先学到这种程度。
用三种状态来描述当前处理过程中节点的情况：

• 如果当前节点尚未被访问，用 $0$ 来标记。
• 如果当前节点正在访问中（也就是当前正在处理与它相关的节点），用$1$来标记。
• 如果当前节点已经访问完毕，用 $2$ 来标记。

如果图中无环，那么不应该出现在处理相关节点的过程中遇到状态为正在访问中的节点的情况。

具体实现

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<Integer>[] graph = new ArrayList[numCourses];Arrays.setAll(graph, i -> new ArrayList<>());// 根据先后要求建图，所给二维数组中的第二个下标表示前置for(int[] item : prerequisites) {graph[item[1]].add(item[0]);}int[] colors = new int[numCourses];for(int i = 0; i < numCourses; i++) {if(colors[i] == 0 && dfs(i, graph, colors)) {return false;}}return true;}// 遍历方法返回的就是图中是否有环private boolean dfs(int cur, List<Integer>[] graph, int[] colors) {// 将当前节点标记为访问中colors[cur] = 1;// 依次访问这个从这个节点出发，能够到达的所有节点for(int next : graph[cur]) {// 判断是否遇到访问中的节点，并递归当前节点// 注意 Java 中逻辑与比逻辑或优先级要高，这里如果没有发生或运算短路，要先计算与if(colors[next] == 1 || colors[next] == 0 && dfs(next, graph, colors)) {return true;}}// 将当前节点标记为已访问过colors[cur] = 2;return false;}
}