娃娃脸3满天星1986：点亮时光，闪耀青春的永恒星辰

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

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

举例如下图所示路线

走到4的时候发现下一个节点2在递归栈中正在访问中访问到了访问过的节点说明遇到环了。

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

2不能只用两种状态表示节点“没有被访问过”和“被访问过”。

举例如上图所示我们先dfs(

再dfs(

此时1的邻居0已经被访问过但这并不能表示此时就找到了环。

Listint[]和ListInteger[]的区别1Listint[]是一个单个的列表列表中的每个元素是一个int[]整型数组相当于一个数组的容器。

2ListInteger[]是一个数组数组的每个元素是一个ListInteger(整数列表)就像是列表的数组。

g[x]存储数据示例// 初始化g [[], [], [], []]// 处理 [1,0] → g[0].add(

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

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

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

g [[1, 2], [3], [3], []]最终g的含义g[0] [1, 2] // 修完课程0后可以修课程1或2g[1] [3] // 修完课程1后可以修课程3g[2] [3] // 修完课程2后可以修课程3g[3] [] // 课程3是终点没有后续课程

复杂度分析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) { // 构造图数组 动态数组 ListInteger[] 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]

{ dfs(i, g, state); } } // ans true 表示图中存在环即不能完成所有课程的学习需要返回false,所以返回 !ans return !ans; } private void dfs(int x, ListInteger[] g, int[] state) { // 2当前顶点已经完全访问完毕。

直接返回 if (state[x]

{ return; } // 1当前顶点正在访问中此时又再次访问到该节点就表示存在环 if (state[x]

{ ans true; return; } state[x] 1; // 标记当前顶点正在访问中 for (int vertex : g[x]) { // 对于当前顶点的每一个邻居 dfs(vertex, g, state); } state[x] 2; // 标记当前顶点访问完毕

该顶点没有邻居

该顶点的 dfs 递归返回了 } }

甜心小丑的vlog在哪里可以看-甜心小丑的vlog在哪里可以看应用