leetcode-6135：图中的最长环_图上找最长环

题目

题目连接
给你一个 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 。
1
2
3
4

示例 2：

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

解题

方法一：内向基环树找环+时间戳

参考链接

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21