leetcode 2360 图中最长的环 题解
题面给定一个有向图，每个点出度最大为一，现在问你图中最长的环的长度是多少，如果没有环输出 -1， 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105。
题面
解题思路
我们直接说结论，我们从任意一个点出发，用一个数组存下来到达每一个点的最短步数，如果发现一个点之前已经被遍历过了，那么这个点一定是一个环的出发点和尽头，环的长度是当前的步数减去这个点的最短步数。
下面稍微证明一下，我们来看标题中给出的条件，每一个点最多只有一条出边，那么这个条件告诉了我们两件事变：
[*]边数比力小；
[*]图中不存在以下情况：
https://i-blog.csdnimg.cn/direct/9026adef1d5e47208494b0320ad5abfb.jpeg
所以当我们遍历的时间，全部颠末的点和边形成的一定是一个链型的布局。当发现有一个点重复遍历的时间，一定是返回到了链上前面的某一个点，形成了一个环，我们统计一下答案就好了。
除此之外我们要注意，标题没有保证任意两点之间可以相互到达，当我们遍历一次之后我们还要查抄还有没有别的点我们没有遍历。
任意两次遍历是互不影响的，大概说一个环只可能出现在详细的一次遍历当中，所以当我们完成一次遍历的时间，直接把这次的点全部都删了就行，否则复杂度就上来了。
代码
class Solution {
public:
int ans = -1; // 最终答案
vector<int> dis; // 存最短步数
void dfs(int x, int D, vector<int>& edges) // D 表示当前步数
{
if (dis != 0) // 如果发现之前被遍历过了，说明可能存在环
{
if (dis == -1) // -1 说明是之前的遍历，不用管
return;
ans = max(ans, D - dis); // 否则就是存在环，记录答案
return;
}
dis = D; // 维护 dis
if (edges != -1)
dfs(edges, D + 1, edges); // 最多只有一个出度，就不用 for 循环了
dis = -1; // 遍历完成开始回溯了，直接把这个点删掉
}
int longestCycle(vector<int>& edges) {
const int N = edges.size();
dis.resize(100005, 0);
for (int i = 0; i < N; i++) // 记得要遍历所有的点
if (dis == 0)
dfs(i, 1, edges);
return ans;
}
};
本人本领有限，如有不当之处敬请指教！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]