leetcode：6135. 图中的最长环【内向基环树 + 最长环板子 + 时间戳】

分析

每个点出度最多是1
所以是一个【弱化】的内向基环图
所有联通分量最多一个环
所有点最多一个环
利用时间戳的方式记录每个点上一次访问的时间
如果有重复访问并且起始时间在st后面，意味着是一个新的环
就记录入案中
同时更新时间戳，和这个点最近的时间戳即可

ac code

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        # 至多一个出边 -》弱化内向基环树
        # 每个联通分量最多只有一个环
        # 每个点最多只有一个环

        # 时间戳 + 边遍历边改优化
        n = len(edges)
        time = [0] * n
        clock, ans = 1, -1

        # x 是起点
        for x, t in enumerate(time):
            if t: continue # 之前已经被动遍历过了
            st = clock
            while x >= 0:
                if time[x]: # 二次遍历x
                    if time[x] >= st: # 找到一个新的环
                        ans = max(ans, clock - time[x])
                    break
                time[x] = clock
                clock += 1
                x = edges[x]
        
        return ans

总结

图论 + 最大环 + 内向基环 + 时间戳