Leetcode - 6135: the longest part of the figure

题目

题目连接
给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边.

图用一个大小为 n 下标从 0 开始的数组 edges 表示,节点 i 到节点 edges[i] 之间有一条有向边.如果节点 i 没有出边,那么 edges[i] == -1 .

请你返回图中的 最长 环,如果没有任何环,请返回 -1 .

一个环指的是起点和终点是 同一个 节点的路径.

示例 1：

输入：edges = [3,3,4,2,3]
输出去：3
解释：The longest part of the figure是：2 -> 4 -> 3 -> 2 .
这个环的长度为 3 ,所以返回 3 .

示例 2：

输入：edges = [2,-1,3,1]
输出：-1
解释：图中没有任何环.

解题

方法一：Within the base ring tree to find ring+时间戳

参考链接

class Solution {
    
public:
    int longestCycle(vector<int>& edges) {
    
        int n=edges.size();
        vector<int> time(n,0);
        int res=-1;
        for(int i=0,clock=1;i<n;i++){
    
            if(time[i]) continue;
            for(int x=i,start_time=clock;x>=0;x=edges[x]){
    
                if(time[x]){
    
                    if(time[x]>=start_time){
    
                        res=max(res,clock-time[x]);
                    }
                    break;
                }
                time[x]=clock++;
            }
        }
        return res;
    }
};