Longest Cycle in a Graph

Hard

You are given a directed graph of n nodes numbered from 0 to n - 1, where each node has at most one outgoing edge.

The graph is represented by a 0-indexed array nums of size n, where nums[i] indicates that there is a directed edge from node i to node nums[i]. If there is no outgoing edge from node i, then nums[i] == -1.

Return the length of the longest cycle in the graph. If no cycle exists, return -1.

Example 1

Input:  nums = [3,3,4,2,3]
Output: 3
Explanation: Nodes 2 → 4 → 3 → 2 form a cycle of length 3.

Example 2

Input:  nums = [2,-1,3,1]
Output: -1
Explanation: No cycle exists.

Example 3

Input:  nums = [-1,4,-1,2,0,4]
Output: -1

Constraints

• n == nums.length
• 1 <= n <= 10^5
• -1 <= nums[i] < n
• nums[i] != i (no self-loops)