hot100 207.课程表

思路：本题相当于给定一个有向图，判断图中是否存在环。

1.判断环：如果在递归的过程中，发现下一个节点在递归栈中（也就是正在访问中），则说明找到了环。

2.举例，如下图所示：路线1->2->3->4->2，走到4的时候，发现下一个节点2在递归栈中（正在访问中），访问到了访问过的节点，说明遇到环了。

3.注意：

（1）本题中，“正在访问中”的节点指的是正在递归处理的节点x及它的后续节点，因为此时dfs（x）尚未结束。

（2）不能只用两种状态表示节点“没有被访问过”和“被访问过”。举例，如上图所示，我们先dfs(0)，再dfs(1)，此时1的邻居0已经被访问过，但这并不能表示此时就找到了环。

List<int[]>和List<Integer>[]的区别：

（1）List<int[]>是一个单个的列表，列表中的每个元素是一个int[]（整型数组），相当于一个数组的容器。

（2）List<Integer>[]是一个数组，数组的每个元素是一个List<Integer>(整数列表)，就像是列表的数组。

g[x]存储数据示例：

// 初始化
g = [[], [], [], []]

// 处理 [1,0] → g[0].add(1)
g = [[1], [], [], []]

// 处理 [2,0] → g[0].add(2)
g = [[1, 2], [], [], []]

// 处理 [3,1] → g[1].add(3)
g = [[1, 2], [3], [], []]

// 处理 [3,2] → g[2].add(3)
g = [[1, 2], [3], [3], []]

最终g的含义：

g[0] = [1, 2] // 修完课程0后，可以修课程1或2
g[1] = [3] // 修完课程1后，可以修课程3
g[2] = [3] // 修完课程2后，可以修课程3
g[3] = [] // 课程3是终点，没有后续课程

5.复杂度分析：

（1）时间复杂度：O(n + m)，其中n是numCourses,m是prerequisites的长度，每个节点至多递归访问一次，每条边至多遍历一次。

（2）空间复杂度：O(n + m)，存储g需要O(n + m)的空间。

附代码：

class Solution { // true表示图中存在环，false表示图中不存在环 private boolean ans = false; public boolean canFinish(int numCourses, int[][] prerequisites) { // 构造图：数组 + 动态数组 List<Integer>[] g = new ArrayList[numCourses]; for (int i = 0;i < numCourses;i++){ g[i] = new ArrayList<>(); } for (int[] p : prerequisites){ g[p[1]].add(p[0]); } // 0：顶点尚未被访问到。 // 1：顶点正在访问中，dfs(x) 尚未结束。 // 2：顶点已经完全访问完毕。 int[] state = new int[numCourses]; // 对每个尚未访问的顶点进行 dfs for (int i = 0; i < numCourses; i++) { if (state[i] == 0) { dfs(i, g, state); } } // ans == true 表示图中存在环，即不能完成所有课程的学习，需要返回false,所以返回 !ans return !ans; } private void dfs(int x, List<Integer>[] g, int[] state) { // 2：当前顶点已经完全访问完毕。直接返回 if (state[x] == 2) { return; } // 1：当前顶点正在访问中，此时又再次访问到该节点，就表示存在环 if (state[x] == 1) { ans = true; return; } state[x] = 1; // 标记当前顶点正在访问中 for (int vertex : g[x]) { // 对于当前顶点的每一个邻居 dfs(vertex, g, state); } state[x] = 2; // 标记当前顶点访问完毕：1、该顶点没有邻居；2、该顶点的 dfs 递归返回了 } }