Overview

This problem asks us to simulate message forwarding starting from member 1 and count how many people receive the message before the same member receives it for the second time.

Analysis

Key Insight

From a graph theory perspective, this problem deals with a special type of graph called a “Functional Graph” where each vertex has exactly one outgoing edge.

Since each member \(i\) always forwards the message to exactly one recipient \(P_i\), starting from member 1 and following the forwarding path, we will eventually return to a member we’ve already visited (by the pigeonhole principle, with only \(N\) people, a duplicate must occur within at most \(N+1\) forwards).

Understanding with a Concrete Example

For example, with \(N = 5\) and \(P = [2, 3, 4, 5, 3]\):

Member 1 → Member 2 → Member 3 → Member 4 → Member 5 → Member 3 (already read!)

Flow of forwarding: 1. Member 1 receives the message (start) 2. Member 2 receives the message 3. Member 3 receives the message 4. Member 4 receives the message 5. Member 5 receives the message 6. Message arrives at Member 3, but they’ve already received it, so we stop

The answer is 5 people.

Approach

A straightforward simulation is sufficient. We follow the forwarding path while keeping track of visited members, and stop when we reach a member who has already been visited.

Algorithm

1. Prepare an array visited to record visited members (initially all False)
2. Set the current member as current = 1
3. Prepare a counter count = 0
4. Repeat the following:
   • If current has been visited, stop
   • Mark current as visited and increment count by 1
   • Update current to the next forwarding destination \(P_{\text{current}}\)
5. Output count

current = 1
while current is not visited:
    mark current as visited
    increment count
    current = P[current]

Complexity

• Time Complexity: \(O(N)\)
  • Since each member is visited at most once, the loop terminates in at most \(N\) iterations
• Space Complexity: \(O(N)\)
  • \(O(N)\) space is needed for the array recording visited members and the array storing forwarding destinations

Implementation Tips

1. Index Adjustment: In the problem, member numbers start from 1, but Python lists start from 0. You can adjust using P[current - 1], or allocate the visited array with size N+1 to handle it with 1-indexed access conveniently.

2. While Loop Condition: Use while not visited[current] so that the loop exits as soon as we reach a visited member. This ensures no second visit occurs.

3. Initial Value Setting: Member 1 is also counted as “a person who received the message,” so don’t forget to include them in the count.

   Source Code

def solve():
    N = int(input())
    P = list(map(int, input().split()))
    
    visited = [False] * (N + 1)
    current = 1
    count = 0
    
    while not visited[current]:
        visited[current] = True
        count += 1
        current = P[current - 1]
    
    print(count)

solve()

---

This editorial was generated by claude4.5opus.