P2661 [NOIP 2015 Senior] Information Transfer

NOIP 2015 Day 1 T2.

There are $n$ players (numbered from $1$ to $n$) playing an information transfer game. In this game, each player has a fixed designated recipient. Specifically, the designated recipient of player $i$ is player $T_i$. At the start of the game, each player knows only their own birthday. Then in each round, all players simultaneously tell all the birthday information they currently know to their designated recipient (note: someone may receive information from several people, but each person tells information to exactly one person, i.e., their designated recipient). The game ends when someone learns their own birthday from someone else. How many rounds can the game proceed in total?

The input consists of $2$ lines. The first line contains $1$ positive integer $n$, representing the number of players. The second line contains $n$ space-separated positive integers $T_1, T_2, \cdots, T_n$. Here, the $i$-th integer $T_i$ means that the designated recipient of player $i$ is player $T_i$, with $T_i \leq n$ and $T_i \neq i$.

Output a single integer on one line, indicating how many rounds the game proceeds in total.

Sample 1 explanation:  The process of the game is shown in the figure. After the $3$rd round, player $4$ will hear player $2$ tell him his own birthday, so the answer is $3$. Of course, after the $3$rd round, player $2$ and player $3$ can also learn their own birthdays from their respective sources, which also satisfies the game’s end condition. Constraints: - For $30\%$ of the testdata, $n \le 200$. - For $60\%$ of the testdata, $n \le 2500$. - For $100\%$ of the testdata, $n \le 2 \times 10^5$. Translated by ChatGPT 5