力扣周赛304 6135. 图中的最长环 内向基环树

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 。

示例 2：

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

提示：

• n == edges.length
• 2 <= n <= 1e5
• -1 <= edges[i] < n
• edges[i] != i

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-cycle-in-a-graph
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

周赛失败，晚上复盘一下子就写出来了T T。本来想问问大佬，然后试一下就出来了

方法：模拟

 

 单指针的图，最后都可以形成一个或多个类似上图的形状，多个外部线连到内部环

当我们从一个指针访问到重复节点的时候，可能得到上面红色线对应的结果，红色线对应的每个点都应该判重，打标记，后续在访问到红色位置访问过的节点时，直接结束

1. 访问到重复节点：记录当前时间戳和旧时间戳的差值结束，同时记录已访问点

2. 访问到非法节点（旧节点访问过的节点）：直接结束，记录已访问点

class Solution {
        public int longestCycle(int[] edges) {
            int n = edges.length;
            boolean[] visited = new boolean[n];
            int ans = -1;
            for(int i = 0; i < n; i++){
                if(visited[i]) continue;
                Map<Integer,Integer> used = new HashMap<>();
                int pos = i;
                int size = 0;
                while (edges[pos]!=-1&&!used.containsKey(edges[pos])&&!visited[edges[pos]]){
                    ++size;
                    pos = edges[pos];
                    used.put(pos,size);
                }
                if(edges[pos]!=-1&&!visited[edges[pos]]){
                    ans = Math.max(ans,size-used.get(edges[pos])+1);
                }
                for(Integer key:used.keySet()){
                    visited[key]=true;
                }
            }
            return ans;
        }
    }