概要

この問題は、各頂点からちょうど1本の有向辺が出ているグラフ（機能グラフ / Functional Graph）において、各頂点から出発してたどり着く「ループ（閉路）」の長さを求める問題です。

考察

各生徒が次にメッセージを渡す相手は一人だけなので、どの生徒から開始しても、いつかは必ずループに到達します。

素朴なアプローチとその限界

すべての生徒 \(i\) について、実際に一人ずつシミュレーションを行う方法が考えられます。しかし、この方法では最悪の場合、1回の探索に \(O(N)\) かかり、全体で \(O(N^2)\) の時間がかかってしまいます。\(N = 2 \times 10^5\) という制約下では、実行時間制限（TLE）に間に合いません。

効率的な解法へのヒント

このグラフの構造には以下の特徴があります： 1. 必ず一つのループに到達する: どの頂点からスタートしても、最終的には一つのループに入り、そこから抜け出すことはありません。 2. 同じパス上の頂点は同じ結果になる: ある生徒 \(A\) から辿った先にループがあるとき、その途中にいる生徒 \(B\) からスタートしても、最終的には同じループに到達します。したがって、一度計算した結果は再利用できます。

この特徴を利用し、一度訪れた頂点の結果を記録（メモ化）しながら探索することで、各頂点を高々数回調べるだけで済むようになります。

アルゴリズム

各頂点の状態を以下の3つの状態で管理しながら、全頂点を走査します。

1. 未訪問 (0): まだ一度も探索されていない。
2. 探索中 (1): 現在のスタート地点からの探索パスに含まれている。
3. 探索完了 (2): 既にどのループに到達するかが判明している。

具体的な手順

1. まだ「未訪問」の生徒 \(i\) を選んで探索を開始します。
2. 「未訪問」の生徒を辿っている間、その生徒を「探索中」にし、パス（訪れた順序）を記録しておきます。
3. 次に進む相手が以下のいずれかの状態になるまで繰り返します：
   • 「探索中」の生徒にぶつかった場合: 新しいループを発見したことを意味します。その生徒がパスの何番目に登場したかを確認することで、ループの長さ（現在のパスの長さ - 登場位置）を計算できます。
   • 「探索完了」の生徒にぶつかった場合: 既に解析済みの構造に合流したことを意味します。その生徒が最終的に到達するループの長さは既に分かっているので、それをそのまま利用します。
4. 探索したパス上のすべての生徒を「探索完了」にし、求めたループの人数を記録します。

これを全生徒に対して行うことで、すべての生徒について効率的に答えを求めることができます。

計算量

• 時間計算量: \(O(N)\) 各頂点と各辺をたどる回数は定数回（「未訪問」から「探索中」、「探索中」から「探索完了」への遷移のみ）であるため、生徒数 \(N\) に対して線形時間で処理が完了します。
• 空間計算量: \(O(N)\) 渡し先の配列、訪問状態の配列、結果の配列、および探索時のパスを保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 再帰の回避: Pythonで深い探索を行う場合、再帰関数を使うとスタックオーバーフロー（RecursionError）が発生する可能性があるため、while ループを用いた反復的な実装が安全です。

• 0-indexed への変換: 入力の生徒番号は \(1\) から \(N\) ですが、プログラム内では \(0\) から \(N-1\) として扱うと、配列のインデックス操作がスムーズになります。

• パス内の位置記録: ループの長さを一瞬で計算するために、現在の探索パスにおいて「どの生徒が何番目に出現したか」を辞書（path_map）などで記録しておくと効率的です。

  ソースコード

import sys

def solve():
    # 入力を一度にすべて読み込みます
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 生徒の数 N
    n = int(data[0])
    
    # 各生徒 i のメッセージの渡し先 T_i
    # 0-indexed に変換して管理します（生徒 1 はインデックス 0、生徒 2 はインデックス 1 ...）
    t = [int(x) - 1 for x in data[1:]]
    
    # 各生徒から開始したときの伝言ループメンバーの人数を格納する配列
    ans = [0] * n
    
    # 訪問状態を管理する配列
    # 0: 未訪問, 1: 現在の探索パスに含まれている, 2: 探索完了済み（確定済み）
    visited = [0] * n
    
    for i in range(n):
        # 既に探索済みの生徒はスキップ
        if visited[i] == 2:
            continue
        
        curr = i
        path = []
        # 現在の探索パス内での生徒の出現位置を記録する辞書
        path_map = {}
        
        # メッセージの伝言をたどる
        while visited[curr] == 0:
            path_map[curr] = len(path)
            path.append(curr)
            visited[curr] = 1
            curr = t[curr]
        
        # 停止したとき、curr は「過去に既にメッセージを受け取ったことのある生徒」
        if visited[curr] == 1:
            # 現在の探索パス内で既に訪れた生徒に到達した場合（新しいループを発見）
            # ループの開始位置を取得
            cycle_start_idx = path_map[curr]
            # ループに含まれる生徒の人数を計算
            cycle_len = len(path) - cycle_start_idx
            # この探索パス上のすべての生徒は、最終的にこのループに到達する
            for node in path:
                ans[node] = cycle_len
        else:
            # 既に探索完了済みの生徒に到達した場合（既存の構造に合流）
            # その生徒が最終的に到達するループの人数をそのまま利用
            cycle_len = ans[curr]
            for node in path:
                ans[node] = cycle_len
        
        # 今回たどったパス上のすべての生徒を探索完了済み（visited = 2）にする
        for node in path:
            visited[node] = 2
            
    # 結果をスペース区切りで出力
    print(*(ans))

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。