说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是处于什么原因，算法学习需要持续保持，今天让我们一起来看看这一道题目————
图中的最长环，图论题目中比较常见的环路问题。
题目描述
给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。
图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。
请你返回图中的 最长 环，如果没有任何环，请返回 -1 。
一个环指的是起点和终点是 同一个 节点的路径。
示例 1：
输入：edges = [3,3,4,2,3] 输出去：3 解释：图中的最长环是：2 -> 4 -> 3 -> 2 。 这个环的长度为 3 ，所以返回 3 。
示例 2：
输入：edges = [2,-1,3,1] 输出：-1 解释：图中没有任何环。
提示：
n == edges.length 2 <= n <= 10^5 -1 <= edges[i] < n edges[i] != i
思路分析
题目的要求很清晰，就是要我们找出单向连通图中的最长环，那么在一个图中我们要怎样来判断有没有存在环呢？因为这道题目中的图是单向图，所以我们可以很简单找出图中的环，如下图：
我们从节点1出发，遍历过的节点都做上标记，然后不断的往图的下一个节点遍历，直到遇到已经做过标记的节点，则说明其前面也遍历过，也即是已经形成了环。这样说的话我们是不是可以把所有节点都当成起点走一遍，找出所有环中的最长环就可以？让我们动手写代码试一下，按照这个思路我们可以写出这样一段代码：
/** * @param {number[]} edges * @return {number} */ var longestCycle = function(edges) { let res = -1; const dfs = (node,steps,step = 0)=>{ if(edges[node] == -1) return -1; if(steps[node] <= step){ res = Math.max(step - steps[node],res); return step; } steps[node] = step; dfs(edges[node],steps,step + 1); } for(let i = 0; i < edges.length; i++){ dfs(i,new Array(edges.length).fill(Infinity)); } return res > 0 ? res : -1; };
测试一下，好像没问题，然后自信提交代码
回头看一下数据规模2 <= n <= 10^5,这样做确实太暴力了，那就来看看可以怎么优化：
上图中橙色路径为从节点1出发的遍历路线，蓝色路径为从节点2出发的遍历路线，从图中我们可以很明显的看成蓝色路线是橙色路线中的一部分，因为节点2在节点1的遍历路径中，所以节点2往后的遍历路线一定是包含在节点1的遍历路线中，所以我们可以记录一下每个节点的遍历情况，如果是已经遍历过的节点的话，我们不应该重复遍历，所以代码可以这样进行优化：
- 使用一个数组来记录遍历过程中每一个节点的遍历情况(visited)
- 使用一个map来存放在当前路径中已经遍历过的节点所需步数(steps)
- 遇到map中存在的节点时更新最长环长度
AC代码
/** * @param {number[]} edges * @return {number} */ var longestCycle = function(edges) { let res = -1; const dfs = (node,steps = {},step = 0)=>{ if(visited[node] || steps[node] <= step || edges[node] == -1){ if(steps[node] < step) res = Math.max(step - steps[node],res); return; } steps[node] = step; visited[node] = true; dfs(edges[node],steps,step + 1); } const visited = new Array(edges.length).fill(false); for(let i = 0; i < edges.length; i++) dfs(i); return res; };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
