概要

メンバー1からメッセージの転送をシミュレーションし、同じメンバーに2回目のメッセージが届くまでに何人がメッセージを受け取ったかを数える問題です。

考察

重要な気づき

この問題は、グラフ理論の観点から見ると「各頂点から出る辺がちょうど1本」という特殊なグラフ（Functional Graph）を扱っています。

各メンバー \(i\) は必ず1人の相手 \(P_i\) にメッセージを転送するため、メンバー1から出発して転送先をたどっていくと、いつか必ず既に訪れたメンバーに戻ってきます（鳩の巣原理より、\(N\) 人しかいないので最大 \(N+1\) 回の転送で必ず重複が発生）。

具体例で理解する

例えば、\(N = 5\)、\(P = [2, 3, 4, 5, 3]\) の場合：

メンバー1 → メンバー2 → メンバー3 → メンバー4 → メンバー5 → メンバー3（既読！）

転送の流れ： 1. メンバー1が受け取る（開始） 2. メンバー2が受け取る 3. メンバー3が受け取る 4. メンバー4が受け取る 5. メンバー5が受け取る 6. メンバー3に届くが、既に受け取っているので終了

答えは 5人 となります。

アプローチ

素朴にシミュレーションすれば十分です。訪問済みかどうかを記録しながら転送先をたどり、既に訪問したメンバーに到達したら終了します。

アルゴリズム

1. 訪問済みを記録する配列 visited を用意（初期値はすべて False）
2. 現在のメンバーを current = 1 とする
3. カウンター count = 0 を用意
4. 以下を繰り返す：
   • current が訪問済みなら終了
   • current を訪問済みにマークし、count を1増やす
   • current を次の転送先 \(P_{\text{current}}\) に更新
5. count を出力

current = 1
while currentが未訪問:
    currentを訪問済みにする
    count を増やす
    current = P[current]

計算量

• 時間計算量: \(O(N)\)
  • 各メンバーは最大1回しか訪問されないため、ループは最大 \(N\) 回で終了します
• 空間計算量: \(O(N)\)
  • 訪問済みを記録する配列と、転送先を格納する配列にそれぞれ \(O(N)\) の空間が必要です

実装のポイント

1. インデックスの調整: 問題ではメンバー番号が1から始まりますが、Pythonのリストは0から始まります。P[current - 1] のように調整するか、visited 配列を N+1 の大きさで確保して1-indexedで扱うと便利です。

2. while文の条件: while not visited[current] として、訪問済みのメンバーに到達した時点でループを抜けます。これにより、2回目の訪問は発生しません。

3. 初期値の設定: メンバー1も「メッセージを受け取った人」に含まれるので、カウントに含めることを忘れないようにしましょう。

   ソースコード

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

---

この解説は claude4.5opus によって生成されました。