概要

各メンバーが「次に送る相手」を 1 人だけ持つ状況で、メンバー 1 から転送を開始し、初めて同じ人に戻ったところで終了するとき、メッセージを受け取った人数を数えます。

考察

この設定は、各頂点（メンバー）から出る辺がちょうど 1 本の有向グラフ（関数グラフ）になっています。
メンバー 1 からたどっていくと、訪問列は

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

のように一意に決まり、いずれ必ず「過去に訪れたメンバー」に到達します（有限個 \(N\) 人しかいないため）。
問題のルールでは「一度受け取ったメンバーに再び届いたら終了」なので、初めて重複が発生する直前までに訪れたユニークな人数を数えれば答えになります。

素朴に「終了するまでシミュレーション」自体は正しいのですが、同じメンバーに戻ったかどうかを毎回リスト検索で確認すると、最悪で \(1 + 2 + \cdots + N = O(N^2)\) になり \(N \le 2 \times 10^5\) では TLE の原因になります。
そこで、各メンバーを訪れたかどうかを配列（真偽値）で管理し、判定を \(O(1)\) にします。

例：\(N=6,\ P = [2,3,4,2,6,5]\)（\(1\rightarrow2\rightarrow3\rightarrow4\rightarrow2\rightarrow\cdots\)）
訪問順は \(1,2,3,4\) で、次が 2（既訪問）なので終了。答えは 4 人です。

アルゴリズム

1. 長さ \(N+1\) の配列 visited を用意し、すべて False で初期化する。
2. cur = 1（現在の保持者）、cnt = 0（受け取った人数）から開始する。
3. visited[cur] が False の間、次を繰り返す：
   • visited[cur] = True として訪問済みにする
   • cnt += 1 する
   • cur = P[cur] に更新する（次の転送先へ進む）
4. ループが止まった時点で cur は既訪問なので転送終了。cnt を出力する。

計算量

• 時間計算量: \(O(N)\)（各メンバーは高々 1 回だけ visited=True になる）
• 空間計算量: \(O(N)\)（visited 配列）

実装のポイント

• 入力の \(P_i\) を 1-indexed で扱うために、P = [0] + ... として先頭にダミーを入れると添字がずれずに済みます。

• ループ条件を while not visited[cur]: にすると、「初めて再訪した瞬間に停止」でき、問題文の終了条件と一致します。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。