概要

各生徒から出発して伝言をたどったとき、最終的に形成されるループの長さを求める問題です。各ノードが出次数1の「Functional Graph（関数グラフ）」の構造を利用して、各ノードが到達するサイクルのサイズを効率的に求めます。

考察

問題の構造を理解する

各生徒 \(i\) には次の渡し先 \(T_i\) がちょうど1つ決まっています。これは各ノードから出る辺がちょうど1本のグラフ、いわゆる Functional Graph です。

Functional Graph には重要な性質があります：

• 各連結成分にはちょうど1つのサイクルが存在する
• サイクルに属さないノードは「しっぽ（tail）」として、サイクルに向かって伸びている

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

1 → 2 → 3 → 4 → 2（サイクル: 2→3→4→2、長さ3）
5 → 4（サイクル 2→3→4→2 に合流）
6 → 5 → 4（同じサイクルに合流）

答えの観察

生徒 \(s\) から出発して \(s, T_s, T_{T_s}, \ldots\) とたどると、いずれ訪問済みのノード \(v\) に到達します。このとき \(v\) から \(v\) に戻るサイクルの長さが答えです。

• \(s\) がサイクル上のノードの場合: \(s\) から出発するとサイクルを一周して \(s\) 自身に戻る。答えはそのサイクルの長さ。
• \(s\) がしっぽ（tail）のノードの場合: たどっていくとサイクルの入口 \(v\) に到達し、一周して再び \(v\) に戻る。答えは到達先のサイクルの長さ。

つまり、どのノードから出発しても、答えはそのノードが最終的に到達するサイクルのサイズです。

素朴なアプローチの問題

各ノードから愚直にたどると、1ノードあたり最大 \(O(N)\) ステップかかり、全体で \(O(N^2)\) となり TLE します。

アルゴリズム

ステップ1: 全サイクルの検出とサイズ計算

各ノードに色を付けて管理します（\(0\): 未訪問、\(1\): 探索中、\(2\): 確定済み）。

1. 未訪問ノード \(s\) から、辺をたどりながらパスを記録する
2. 探索中（色 \(1\)）のノードに到達したら、新しいサイクルを発見。パス上でそのノードから末尾までがサイクル
3. 確定済み（色 \(2\)）のノードに到達したら、パス上の全ノードはしっぽ

ステップ2: 各しっぽノードの到達サイクルを特定

サイクル上のノードには既にサイクルIDが分かっています。しっぽノードについては、辺をたどってサイクルIDが判明しているノードに到達するまで進み、パス上の全ノードに同じサイクルIDを記録します（経路圧縮）。

最終的に \(ans[i] = \) ノード \(i\) が到達するサイクルのサイズ、として出力します。

計算量

• 時間計算量: \(O(N)\) — 各ノードは定数回しか訪問されない（ステップ1、ステップ2それぞれで各ノード最大1回処理）
• 空間計算量: \(O(N)\) — 色配列、サイクルID配列、パス記録用の配列など

実装のポイント

• 再帰を使わずイテレーティブに処理: \(N\) が最大 \(2 \times 10^5\) と大きいため、再帰ではスタックオーバーフローの危険がある。while ループで経路をたどる。

• 色による3状態管理: 「未訪問」「探索中」「確定済み」の3色を使うことで、サイクルの開始点を正確に特定できる。

• 経路圧縮: ステップ2でしっぽノードを処理する際、一度たどったパス上の全ノードにサイクルIDを一括設定することで、同じノードを何度もたどることを防ぐ。

  ソースコード

import sys
from sys import setrecursionlimit

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    T = [int(input_data[i+1]) - 1 for i in range(N)]
    
    # For each node, we need to find which cycle it eventually reaches, and the size of that cycle.
    # Since each node has exactly one outgoing edge (functional graph), the structure is
    # a set of connected components each with exactly one cycle (rho-shaped).
    
    # Step 1: Find all cycles and their sizes.
    # We use a coloring approach:
    # 0 = unvisited, 1 = in progress, 2 = done
    
    color = [0] * N
    cycle_id = [-1] * N  # which cycle does this node belong to (if on a cycle)
    cycle_sizes = []  # size of each cycle
    
    # For nodes on a cycle, cycle_id[node] = index into cycle_sizes
    # For nodes not on a cycle (tails), cycle_id remains -1
    
    for s in range(N):
        if color[s] != 0:
            continue
        # Trace the path from s
        path = []
        node = s
        while color[node] == 0:
            color[node] = 1
            path.append(node)
            node = T[node]
        
        if color[node] == 1:
            # We found a new cycle. Find where the cycle starts in path.
            cycle_start = node
            idx = len(path) - 1
            while path[idx] != cycle_start:
                idx -= 1
            cycle_len = len(path) - idx
            cid = len(cycle_sizes)
            cycle_sizes.append(cycle_len)
            for j in range(idx, len(path)):
                cycle_id[path[j]] = cid
                color[path[j]] = 2
            # Mark tail nodes as done
            for j in range(idx):
                color[path[j]] = 2
        else:
            # color[node] == 2, all nodes in path are tails leading to already processed component
            for j in range(len(path)):
                color[path[j]] = 2
    
    # Step 2: For each node, find which cycle it reaches and the cycle size.
    # Nodes on a cycle: answer when starting from them = cycle size (they are on the cycle, 
    #   and following from them leads around the cycle back to themselves).
    # Wait, actually no. The problem says: start from s, follow the chain, and when you 
    # revisit a node v, the cycle from v back to v is the answer.
    # If s is on a cycle of size L, then starting from s, after L steps you return to s. Answer = L.
    # If s is a tail node, following from s eventually enters the cycle at some node v, 
    #   and then goes around the cycle back to v. Answer = cycle size.
    # So actually the answer for every node is just the size of the cycle it eventually reaches!
    
    # We need to find for each tail node, which cycle it reaches.
    # We can do this by following pointers until we hit a node with cycle_id != -1.
    # To avoid repeated work, we memoize.
    
    ans = [0] * N
    
    # For nodes on a cycle, answer is their cycle size
    for i in range(N):
        if cycle_id[i] != -1:
            ans[i] = cycle_sizes[cycle_id[i]]
    
    # For tail nodes, follow until we find a node with known answer
    # Use iterative path compression
    reach_cycle = [-1] * N  # which cycle each node reaches
    for i in range(N):
        if cycle_id[i] != -1:
            reach_cycle[i] = cycle_id[i]
    
    for i in range(N):
        if reach_cycle[i] != -1:
            continue
        # Trace from i
        path = []
        node = i
        while reach_cycle[node] == -1:
            path.append(node)
            node = T[node]
        cid = reach_cycle[node]
        for p in path:
            reach_cycle[p] = cid
            ans[p] = cycle_sizes[cid]
    
    sys.stdout.write(' '.join(map(str, ans)) + '\n')

main()

---

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