Overview

In a situation where each member has exactly one “next person to send to,” message forwarding starts from Member 1 and ends when the message first returns to someone who has already received it. We need to count the number of people who received the message.

Analysis

This setting forms a directed graph (functional graph) where each vertex (member) has exactly one outgoing edge.
Starting from Member 1 and following the chain, the sequence of visits is uniquely determined as:

\(1 \rightarrow P_1 \rightarrow P_{P_1} \rightarrow \cdots\)

and it will inevitably reach “a member who has already been visited” (since there are only a finite number \(N\) of people).
According to the problem’s rules, “the process ends when the message reaches a member who has already received it,” so the answer is the number of unique people visited just before the first duplicate occurs.

Simply “simulating until termination” is correct in principle, but if we check whether the same member has been visited by searching through a list each time, the worst case becomes \(1 + 2 + \cdots + N = O(N^2)\), which causes TLE for \(N \le 2 \times 10^5\).
Therefore, we manage whether each member has been visited using an array (of boolean values), making each check \(O(1)\).

Example: \(N=6,\ P = [2,3,4,2,6,5]\) (\(1\rightarrow2\rightarrow3\rightarrow4\rightarrow2\rightarrow\cdots\))
The visit order is \(1,2,3,4\), and the next would be 2 (already visited), so the process ends. The answer is 4 people.

Algorithm

1. Prepare an array visited of length \(N+1\) and initialize all entries to False.
2. Start with cur = 1 (current holder) and cnt = 0 (number of people who received the message).
3. While visited[cur] is False, repeat the following:
   • Set visited[cur] = True to mark it as visited.
   • Increment cnt += 1.
   • Update cur = P[cur] (move to the next forwarding destination).
4. When the loop stops, cur has already been visited, so forwarding ends. Output cnt.

Complexity

• Time complexity: \(O(N)\) (each member is set to visited=True at most once)
• Space complexity: \(O(N)\) (the visited array)

Implementation Notes

• To handle the input \(P_i\) with 1-indexed access, prepending a dummy element as P = [0] + ... avoids index offset issues.

• Setting the loop condition to while not visited[cur]: ensures that “it stops the moment a revisit first occurs,” which matches the termination condition described in the problem.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    P = [0] + list(map(int, input().split()))
    visited = [False] * (N + 1)

    cur = 1
    cnt = 0
    while not visited[cur]:
        visited[cur] = True
        cnt += 1
        cur = P[cur]

    print(cnt)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.