The Lost Link
You're helping a student organization manage their alumni network. The network is represented as a directed graph where each student points to exactly one other student (or themselves). This structure is given as an array next_student, where next_student[i] is the student that student i points to. Starting from student 0, you follow the links. You need to find the first student who is part of a cycle, or determine if no cycle exists starting from student 0.
If student 0 is part of a cycle, output the index of the first student in that cycle encountered when starting from student 0. If student 0 is not part of a cycle, but leads to a student who is part of a cycle, output the index of the first student in that cycle encountered. If there's no cycle reachable from student 0, output -1.
Input
The first line contains an integer N, the number of students. The second line contains N space-separated integers representing the next_student array. next_student[i] is the student that student i points to.
Output
Print a single integer: the index of the first student in the cycle reachable from student 0, or -1 if no such cycle exists.
Constraints
1 <= N <= 200000 0 <= next_student[i] < N for all i
Example 1
5 1 2 3 4 1
1
The path is 0 -> 1 -> 2 -> 3 -> 4 -> 1. Student 1 is the first in the cycle.
Example 2
3 1 2 0
0
The path is 0 -> 1 -> 2 -> 0. Student 0 is the first in the cycle.
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
3 1 2 0