Cycle Detection and Rendezvous
You are given a structure that behaves like a singly linked list, but it's represented using arrays. Specifically, you have an array next_idx of size $N$, where next_idx[i] stores the index of the next element in the sequence starting from index $i$. The sequence starts at index 0. The structure is guaranteed to eventually enter a cycle. Find the index of the first node that is part of the cycle. If the cycle starts at index 0, output 0.
Input
The first line contains an integer $N$ (the size of the next_idx array). The second line contains $N$ integers, representing the next_idx array.
Output
Print a single integer: the index of the first node that is part of the cycle.
Constraints
1 <= N <= 200000 0 <= next_idx[i] < N for all i
Example 1
8 1 2 3 4 5 6 7 2
2
The sequence is 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 2. The cycle starts at index 2.
Example 2
5 1 2 3 4 0
0
The sequence is 0 -> 1 -> 2 -> 3 -> 4 -> 0. The cycle starts at index 0.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
8 1 2 3 4 5 6 7 2
5 1 2 3 4 0