leetcode 2360 图中最长的环 题解

题面

给定一个有向图，每个点出度最大为一，现在问你图中最长的环的长度是多少，如果没有环输出 -1，                                   1                         ≤                         n                         ≤                         1                                   0                            5                                       1 \le n \le 10^5                  1≤n≤105。
题面
解题思路

我们直接说结论，我们从任意一个点出发，用一个数组存下来到达每一个点的最短步数，如果发现一个点之前已经被遍历过了，那么这个点一定是一个环的出发点和尽头，环的长度是当前的步数减去这个点的最短步数。
下面稍微证明一下，我们来看标题中给出的条件，每一个点最多只有一条出边，那么这个条件告诉了我们两件事变：

• 边数比力小；
  
• 图中不存在以下情况：
  
  
  
  

所以当我们遍历的时间，全部颠末的点和边形成的一定是一个链型的布局。当发现有一个点重复遍历的时间，一定是返回到了链上前面的某一个点，形成了一个环，我们统计一下答案就好了。
除此之外我们要注意，标题没有保证任意两点之间可以相互到达，当我们遍历一次之后我们还要查抄还有没有别的点我们没有遍历。
任意两次遍历是互不影响的，大概说一个环只可能出现在详细的一次遍历当中，所以当我们完成一次遍历的时间，直接把这次的点全部都删了就行，否则复杂度就上来了。
代码

1. class Solution {
2. public:
3.     int ans = -1; // 最终答案
4.     vector<int> dis; // 存最短步数
6.     void dfs(int x, int D, vector<int>& edges) // D 表示当前步数
7.     {
8.         if (dis[x] != 0) // 如果发现之前被遍历过了，说明可能存在环
9.         {
10.             if (dis[x] == -1) // -1 说明是之前的遍历，不用管
11.                 return;
12.             ans = max(ans, D - dis[x]); // 否则就是存在环，记录答案
13.             return;
14.         }
15.         dis[x] = D; // 维护 dis
16.         if (edges[x] != -1)
17.             dfs(edges[x], D + 1, edges); // 最多只有一个出度，就不用 for 循环了
18.         dis[x] = -1; // 遍历完成开始回溯了，直接把这个点删掉
19.     }
21.     int longestCycle(vector<int>& edges) {
22.         const int N = edges.size();
23.         dis.resize(100005, 0);
24.         for (int i = 0; i < N; i++) // 记得要遍历所有的点
25.             if (dis[i] == 0)
26.                 dfs(i, 1, edges);
27.         return ans;
28.     }
29. };

复制代码

本人本领有限，如有不当之处敬请指教！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。