Cycle Lengths
Time: 1.0 s Memory: 1024 MB
-
There is a strange house with $N$ rooms, numbered from $1$ to $N$. From every room, there is exactly one directed corridor leaving it. Thus, from every room, you can only go to exactly one room. Multiple corridors can of course point into the same room.
Suppose you start at room $i$ and traverse corridors until you reach a room that you have seen before. Let the number of corridors you traverse be $f(i)$.
Your task is to compute $f(i)$ for every room.
Input
The first line of input contains the integer $N$ ($1 \leq N \leq 1000$).
The following line contains $N$ integers $e_1, \dots , e_N$ ($1 \leq e_i \leq N$), where $e_i$ means that room $i$ has a directed corridor to room $e_i$.
Output
Print $f(i)$ for each $i$ where $1 \leq i \leq N$.
Sample Input 1 Sample Output 1 1 1
1
Sample Input 2 Sample Output 2 4 2 3 4 1
4 4 4 4
Sample Input 3 Sample Output 3 4 2 3 4 3
4 3 2 2
-
To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.
You must log in to register. - Cycle Lengths