概要

メンバー間でメッセージが転送され、既読になったメンバーには再び送られないとき、メンバー1から始まる転送で何人がメッセージを受け取るかを求める問題。

考察

この問題は、メンバー \(1\) から始まる一連のメッセージの転送経路を追跡し、すでに訪れたことのあるメンバーに再度到達するまでに何人を通ったかを数えるものです。

メッセージの転送は、各メンバー \(i\) が次に送る相手 \(P_i\) が一意に決まっているため、これは「有向グラフ」における探索と考えることができます。各頂点（メンバー）からはちょうど1本の有向辺（転送先）が出ているので、このようなグラフは「機能グラフ（Functional Graph）」とも呼ばれます。

メンバー1から出発し、まだ訪れていないメンバーを順にたどっていきます。もし既に訪れたことがあるメンバーに到達したら、そこで終了です。このとき、訪れた回数が答えになります。

素朴な方法として、毎回リストの中を探索して「既に訪れたか」を確認するような実装をすると、最悪ケースで \(O(N^2)\) の計算量になり、制約 \(N \leq 2 \times 10^5\) では間に合いません。そこで、「既読かどうか」を高速に判定するために、サイズ \(N+1\) の visited 配列を用意し、各メンバーに対応するインデックスに True/False を記録することで、定数時間で判定できるようにします。

アルゴリズム

1. 各メンバーの転送先 \(P_i\) を読み込む。
2. メンバー1からスタートし、以下の処理を繰り返す：
   • 現在のメンバーが既読なら終了。
   • そうでなければ、そのメンバーを既読にしてカウントを増やす。
   • 次のメンバーに移動（\(P_{\text{current}}\) に移動）。
3. カウントを出力する。

このアルゴリズムにより、メンバー1から始まる一意のパスを効率よく追うことができます。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

各メンバーは最大でも1度しか訪れないため、whileループのステップ数は最大 \(N\) 回です。また、visited 配列もサイズ \(N+1\) なので、空間計算量も \(O(N)\) です。

実装のポイント

• メンバー番号は1-indexedなので、配列アクセスの際には P[current - 1] のように1を引く必要がある。
• visited 配列を使うことで、「既読判定」を高速に行えるようにする。
• 入力を高速に読み込むために sys.stdin.read を使用している。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = list(map(int, data[1:]))
    
    visited = [False] * (N + 1)
    current = 1
    count = 0
    
    while not visited[current]:
        visited[current] = True
        count += 1
        current = P[current - 1]
    
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。