LeetCode2360最长环示例，如何改写为长尾词？

本文共计1527个文字，预计阅读时间需要7分钟。

目录+主题描述+整理题意+解题思路分析+具体实现+复杂度分析+代码实现+总结+主题描述+主题链接：

2360. 图中的最长环+给你一个+n+个节点的有向图，节点的编号为0到+n-1，+每个节点都有一个指向的节点，表示有向边。+你需要找到图中最长的一条环。+环的长度定义为环中节点的数量。+节点编号为0的节点为起点。++解题思路：+1. 使用深度优先搜索（DFS）遍历图，记录每个节点的访问状态。+2. 在DFS过程中，检测环的存在，并计算环的长度。+3. 使用一个数组来存储每个节点的父节点，用于判断环的起点。+4. 遍历所有节点，找到最长的环。++具体实现：++复杂度分析：++代码实现：++总结：++主题描述：++主题链接：+

目录

• 题目描述
• 整理题意
• 解题思路分析
• 具体实现
• 复杂度分析
• 代码实现
• 总结

题目描述

题目链接：2360. 图中的最长环

给你一个 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，表示节点 i 到节点 edges[i] 之间有一条有向边（ i 指向 edges[i]）。

规定如果节点i没有出边，那么edges[i] == -1。

题目让我们返回图中 最长的环，如果图中不存在环返回 -1。

解题思路分析

因为该题所给的图为有向图，且每个节点至多只有一条出边，我们可以从任意一个节点出发，如果能够到达 本轮 已经遍历过的节点，那么说明能够构成一个新环。维护环的最大值即可。

具体实现

那么我们要怎么记录遍历过的节点是否为本轮遍历过的节点呢？

• 很容易想到每次都清空一遍标记数组，但是因为题目数据范围的原因，这样做是会超时的。

正确做法：利用一个时间戳来表示每个节点是第几个被遍历到的，那么我们只需记录本轮开始节点的时间戳，当遇到已经遍历过的节点时判断该节点的时间戳与本轮开始节点的时间戳大小关系即可：

• 如果大于等于本轮开始节点的时间戳：说明是本轮遍历到新的一个环；
• 否则仅仅表示遍历到之前遍历过的节点，没有构成新的环（因为之前遍历过的节点如果有环也已经记录过了）

初始化环的最大值为 -1，期间不断维护环的最大值即可，最后返回这个最大值即可。

复杂度分析

• 时间复杂度：O(n)，其中n为edges的长度，也就是点的个数。
• 空间复杂度：O(n)。

代码实现

class Solution { public: int longestCycle(vector<int>& edges) { int n = edges.size(); // mp[i] = j 表示节点 i 是第 j 个遍历到的 int mp[n]; memset(mp, 0, sizeof(mp)); int ans = -1; // k 进行计数 int k = 1; for(int i = 0; i < n; i++){ // 从没有遍历过的点作为起点 if(mp[i] == 0){ int t = i; // 找到第一个遍历过的节点 while(mp[t] == 0){ mp[t] = k++; t = edges[t]; if(t == -1) break; } // 利用时间戳计算环的长度，取最大值 if(t != -1 && mp[t] >= mp[i]){ ans = max(ans, k - mp[t]); } } } return ans; } };

总结

• 该题的核心思想为记录每个节点被遍历到的时间戳，通过 时间戳来实现找新环的逻辑。
• 因为是有向图且每个节点至多有一个出度，所以可以利用时间戳的方式来实现，需要注意这个前提条件。

测试结果：

以上就是C C++ 题解LeetCode2360图中的最长环示例的详细内容，更多关于C C++ 图中的最长环的资料请关注自由互联其它相关文章！