Array Linked List Simulation
You are given an array representing a linked list. The array next_arr of size N is such that next_arr[i] is the index of the next element after index i. The first element is at index 0. An element with next_arr[i] == -1 is the end of the list. Some elements might be unreachable from index 0. Some elements might form a cycle. Your task is to find the length of the longest path starting from index 0, and also detect if there is a cycle reachable from index 0. If a cycle is reachable, output the length of the cycle. If no cycle is reachable, output the length of the longest path. If the list is empty (N=0), output 0.
Input
The first line contains an integer N, the size of the next_arr. The second line contains N space-separated integers representing the next_arr.
Output
A single integer: the length of the longest path from index 0, or the length of the cycle reachable from index 0.
Constraints
1 <= N <= 200000. next_arr[i] is an integer between -1 and N-1, inclusive. next_arr[0] is always between 0 and N-1, inclusive.
Example 1
5 1 2 3 4 -1
5
A simple linear list: 0 -> 1 -> 2 -> 3 -> 4. Longest path is 4.
Example 2
5 1 2 3 1 -1
3
A cycle is formed: 0 -> 1 -> 2 -> 3 -> 1. Cycle is 1 -> 2 -> 3 -> 1. Cycle length is 3.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 3 4 -1
5 1 2 3 1 -1