难度: Hard
给你一个 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.length2 <= n <= 105-1 <= edges[i] < nedges[i] != i运行时间: 134 ms
内存: 27.8 MB
class Solution:
def longestCycle(self, edges: List[int]) -> int:
n = len(edges)
ans, clock = -1, 1
times = [0] * n
for x, t in enumerate(times):
if t: continue #已经访问过了
start_time = clock
while x >= 0:
if times[x]:
if times[x] >= start_time:
ans = max(ans, clock - times[x])
break
times[x] = clock
clock += 1
x = edges[x]
return ans
题解使用了一个遍历标记法来检测并记录图中的环。首先，定义一个数组 times 来存储每个节点第一次被访问的时间。遍历图中的每个节点，如果节点已经被访问过，则跳过。对于未访问的节点，从该节点出发，遍历其路径。如果遇到已经访问过的节点，检查这个节点的访问时间是否在当前搜索开始之后，如果是，说明找到了一个环，并用当前时间减去该节点的访问时间来计算环的长度，更新最大环长。若遇到的已访问节点不在当前搜索开始之后，表示此次搜索没有发现新的环，停止当前路径的搜索。这个过程重复直到所有节点都被检查。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def longestCycle(self, edges: List[int]) -> int:
n = len(edges) # 获取节点总数
ans, clock = -1, 1 # 初始化最大环长度和时间戳
times = [0] * n # 初始化访问时间数组
for x, t in enumerate(times):
if t: continue # 如果当前节点已访问，跳过
start_time = clock # 记录当前路径的开始时间
while x >= 0: # 遍历当前节点的路径
if times[x]: # 如果访问过当前节点
if times[x] >= start_time: # 检查是否在本次搜索中访问过
ans = max(ans, clock - times[x]) # 更新最大环长度
break
times[x] = clock # 标记节点访问时间
clock += 1 # 更新时间戳
x = edges[x] # 移动到下一个节点
return ans
是的，这里的逻辑确实是这样的。在这种检测环的方法中，只有在当前的搜索路径中之前访问过的节点才会被考虑形成环。这是因为times数组记录了每个节点第一次被访问的时间戳，而start_time记录了当前路径搜索的开始时间。如果在搜索过程中遇到一个已经访问过的节点，并且该节点的访问时间大于等于start_time，这意味着这个节点在当前的搜索路径中被访问过，因此在这两个节点之间形成了一个环。
在题解的算法中，如果一个节点i没有出边（即`edges[i] == -1`），那么在代码中`x = edges[x]`这一行将会使x变为-1。代码中的循环条件是`while x >= 0`，因此当x变为-1时，循环将自动停止，不会继续搜索或者错误地计算环的长度。这种处理方式确保了在遇到没有出边的节点时，搜索能够正确地停止。
题解算法通过检查节点的访问时间来确定是否形成了环，并且一旦检测到环，通过`break`语句立即退出当前的while循环，这样可以及时停止当前路径的搜索。这种方法有效地避免了在环被检测到后继续无用的遍历。一旦环的存在被确认，没有必要继续遍历当前路径中的其他节点，因为这不会发现新的环或更长的环，从而确保了算法的效率。