概要

各生徒が「次に渡す相手」をちょうど 1 人持つグラフ（Functional Graph）上で、開始点ごとに最終的に到達する ループ（閉路）の長さ を求める問題です。

考察

重要な観察

• 各頂点（生徒）から出る辺は 1 本（\(i \to T_i\)）なので、グラフは いくつかのループ と、そこへ流れ込む 木（鎖） の集合になります。
• どの生徒から始めても、辿り続けると必ずどこかのループに入ります。
• 伝言が停止したときの「伝言ループメンバーの人数」は、最終的に入った ループの頂点数（閉路長） そのものです。
  ループに入る前に通った鎖の部分は人数に含まれません。

素朴解がなぜダメか

各開始点 \(s\) について、訪問管理をしながら \(s, T_s, T_{T_s}, \dots\) をシミュレーションすると、 - 最悪で 1 回のシミュレーションが \(O(N)\) - それを \(N\) 回やるので \(O(N^2)\)
となり、\(N \le 2\times 10^5\) では TLE になります。

解決方針

1. ループ上の頂点だけを先に特定し、その閉路長を答えとして確定する
   
2. ループ以外の頂点（鎖の部分）は、最終的に流れ着くループは 1 つに決まるので、逆向き辺を使って答えを伝播させる

このために「入次数 0 の頂点を削る」処理（トポロジカル除去）を使うと、ループ部分だけをきれいに残せます。

アルゴリズム

1) 逆辺と入次数を作る

• 辺 \(i \to T_i\) を張る
• 入次数 indeg[x]（何人が x に渡すか）を数える
• 逆辺リスト rev[x] = [x に向かう元の頂点たち] を作る
  これは後で「ループから外側へ答えを広げる」のに使います。

2) 入次数 0 の頂点をキューで削っていく（ループ以外を除去）

入次数 0 の頂点は 絶対にループに入れない（誰からも来ないので閉路を作れない）ため、鎖側の頂点です。 - 入次数 0 をキューに入れる - 取り出して、その行き先 to = T[v] の入次数を 1 減らす - それで入次数が 0 になったら次にキューへ

これを繰り返すと、最後に indeg[i] > 0 で残った頂点は 全てループ上 になります。

3) 残ったループを辿って閉路長を確定

indeg[i] > 0 かつ未確定の頂点から、 - i -> T[i] -> T[T[i]] -> ... と辿ると必ず元の i に戻り、ループが 1 周できます - そのときに集めた頂点数が閉路長 - ループ上の各頂点の答え ans[v] に閉路長を入れる

4) 逆辺でループ長を鎖部分に伝播（幅優先探索）

ループ上の頂点は答えが確定済みなので、それらをキューに入れて、 - キューから v を取り出す - rev[v]（v に向かう元の頂点）について、まだ答えが未確定なら ans[u] = ans[v] としてキューに追加

こうすると、ループから外側へ順に「最終的に入るループの長さ」が全頂点へ伝播します。

具体例

例えば
\(1\to2,\ 2\to3,\ 3\to2,\ 4\to3\) のとき、ループは \((2,3)\) で長さ 2。 - 2,3 の答えは 2 - 1 は 1→2 でそのループに入るので答え 2 - 4 は 4→3 でそのループに入るので答え 2
全員 2 になります。

計算量

• 時間計算量: \(O(N)\)
  （各頂点・各辺を定数回ずつ処理するだけ）
• 空間計算量: \(O(N)\)
  （入次数配列・逆辺リスト・キュー・答え配列）

実装のポイント

• 頂点番号が \(1\sim N\) なので、配列は 1-indexed（先頭にダミー 0）にするとミスが減ります。

• 「ループ検出」は DFS で頑張るより、入次数 0 除去でループだけ残すと簡単かつ高速です。

• 伝播は rev（逆辺）を使うのが重要です。順方向だと「外側へ」広がれません。

• ループ長確定後、ループ頂点を初期値として BFS すると、鎖部分も漏れなく埋まります。

  ソースコード

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    T = [0] + data[1:1 + N]

    indeg = [0] * (N + 1)
    rev = [[] for _ in range(N + 1)]
    for i in range(1, N + 1):
        to = T[i]
        indeg[to] += 1
        rev[to].append(i)

    q = deque(i for i in range(1, N + 1) if indeg[i] == 0)
    while q:
        v = q.popleft()
        to = T[v]
        indeg[to] -= 1
        if indeg[to] == 0:
            q.append(to)

    ans = [0] * (N + 1)

    # Assign cycle lengths to cycle nodes (nodes with indeg > 0 after pruning)
    for i in range(1, N + 1):
        if indeg[i] > 0 and ans[i] == 0:
            cycle = []
            cur = i
            while True:
                cycle.append(cur)
                cur = T[cur]
                if cur == i:
                    break
            clen = len(cycle)
            for v in cycle:
                ans[v] = clen

    # Propagate cycle lengths to non-cycle nodes via reverse edges
    q = deque(v for v in range(1, N + 1) if ans[v] > 0)
    while q:
        v = q.popleft()
        for u in rev[v]:
            if ans[u] == 0:
                ans[u] = ans[v]
                q.append(u)

    print(" ".join(map(str, ans[1:])))

if __name__ == "__main__":
    main()

---

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