↓Skip to main content
  1. Posts/

LeetCode-2360 图中的最长环

·1 min·
Table of Contents

LeetCode-2360 图中的最长环 #

Solution 1 #

使用时间戳来记录访问到某些的点的时间. 时间戳之差即为环的长度.

代码如下:

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        cur_time = 0
        vis_time = [0] * n
        ans = -1
        for x in range(n):
            start_time = cur_time
            while x != -1 and vis_time[x] == 0:
                vis_time[x] = cur_time
                cur_time += 1
                x = edges[x]
            if x != -1 and vis_time[x] >= start_time:
                ans = max(ans, cur_time - vis_time[x])
        return ans