Overview

Given \(N\) members who forward messages sequentially according to rules, the problem asks how many members in total have received the message by the time someone receives the message for the second time (i.e., it becomes “already read”).

Analysis

In graph theory terms, this problem is about simulating traversal in a “directed graph where each vertex has out-degree 1.”

Key Observations

1. Termination condition: The forwarding stops the moment someone receives the message for the “second time.” This means we need to record the members (vertices) that have been visited and check whether we reach a member that has already been visited.
2. Counting people: Messages are passed one person at a time in order. Each time the message is passed to a new member who hasn’t received it yet, we increment the count by \(+1\).
3. Complexity: The number of members \(N\) is at most \(2 \times 10^5\). Since the simulation ends as soon as a previously visited member is visited again, the number of simulation steps is at most about \(N\). Therefore, naively tracing the forwarding one person at a time is sufficiently fast.

Concrete Example

Consider the case where \(N=4\) and the forwarding destinations are \(P_1=2, P_2=3, P_3=4, P_4=2\). - Member 1 receives the message (1st person: read [1]) - Forward from 1 to \(P_1=2\). Member 2 receives the message (2nd person: read [1, 2]) - Forward from 2 to \(P_2=3\). Member 3 receives the message (3rd person: read [1, 2, 3]) - Forward from 3 to \(P_3=4\). Member 4 receives the message (4th person: read [1, 2, 3, 4]) - Forward from 4 to \(P_4=2\). Member 2 has already read the message, so we stop here. - Result: 4 people

Algorithm

1. Managing read status: Prepare a boolean array visited of length \(N+1\), initialized entirely to False.
2. Simulation:
   • Set the current member current to 1 and the count count to 0.
   • While visited[current] is False, repeat the following operations:
     1. Set visited[current] to True (mark as read).
     2. Increment count by 1.
     3. Update current to the next forwarding destination \(P_{current}\).
3. Output: Output the value of count when the loop terminates.

Complexity

• Time complexity: \(O(N)\)
  • We trace the message forwarding one step at a time. Since each member is visited at most once, the process finishes in time proportional to the number of members \(N\).
• Space complexity: \(O(N)\)
  • Memory proportional to \(N\) is used to store the forwarding destination list \(P\) and the array visited that records the read status.

Implementation Notes

• Handling 1-indexed values: In the problem statement, member numbers are given from 1 to \(N\). Since Python lists start from 0, adjusting the index with something like p[current - 1], or making the list size \(N+1\), helps prevent mistakes.

• Efficient input: Since \(N\) can be large, reading all input at once using sys.stdin.read().split() or similar methods results in faster execution.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # メンバーの人数 N を取得
    n = int(input_data[0])
    # 各メンバー i の転送先 P_i のリストを取得
    # P[i-1] が メンバー i の転送先 P_i に対応します
    p = list(map(int, input_data[1:]))
    
    # メッセージを受け取ったかどうかを記録する配列（1-indexedに対応するため n+1 サイズ）
    visited = [False] * (n + 1)
    
    # メンバー 1 から転送を開始
    current = 1
    count = 0
    
    # まだメッセージを受け取っていないメンバーである限り転送を続ける
    while not visited[current]:
        # 現在のメンバーを「既読」にする
        visited[current] = True
        # 受け取った人数をカウント
        count += 1
        # 次の転送先メンバーを更新
        # メンバー i の転送先は P_i (リストでは p[i-1])
        current = p[current - 1]
        
    # メッセージを受け取った延べ人数（ユニークな人数）を出力
    print(count)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.