Leicester Weekly 304 6135. The longest ring in the picture Inward base ring tree

6135. Longest loop in the figure

Give you a directed graph of n nodes, nodes numbered 0 to n - 1, where each node has at most one outgoing edge.

The graph is represented by an array edges of size n with subscripts starting at 0, nodes i toThere is a directed edge between the nodes edges[i].If node i has no outgoing edges, then edges[i] == -1 .

Please return the longest ring in the figure. If there is no ring, please return -1 .

A ring is a path that starts and ends at the same node.

Example 1:

Input:edges = [3,3,4,2,3]Output to:3Explanation: The longest cycle in the graph is: 2 -> 4 -> 3 -> 2 .The length of this ring is 3 , so 3 is returned.

Example 2:

Input:edges = [2,-1,3,1]Output:-1Explanation: There are no cycles in the graph.

Tip:

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

Source: LeetCode
Link: https://leetcode.cn/problems/longest-cycle-in-a-graph
The copyright belongs to LeetCode.For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.

Results of the questions

Failed in the weekly competition, and I wrote T T after reviewing the game at night.Originally wanted to ask the big guy, and then tried it out

Method: Simulate

A single-pointer graph can eventually form one or more shapes similar to the above, with multiple outer lines connected to the inner ring

When we visit a duplicate node from a pointer, we may get the result corresponding to the red line above. Each point corresponding to the red line should be judged and marked, and then when we visit the node that has been visited at the red position, end directly

1. Access to a duplicate node: end of recording the difference between the current timestamp and the old timestamp, and record the visited point at the same time

2. Visiting an illegal node (a node visited by the old node): end directly, record the visited point

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 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;}}