概要

各花火 \(i\) を打ち上げると対象 \(T_i\) が消滅する構造は「各ノードの出次数が1の有向グラフ（functional graph）」を成します。打ち上げ済みの花火数を最大化する問題は、このグラフに含まれるサイクルの数を数える問題に帰着され、答えは \(N - (\text{サイクルの数})\) となります。

考察

グラフ構造の理解

各花火 \(i\) から花火 \(T_i\) へ辺を張ると、すべてのノードの出次数がちょうど1の有向グラフ（functional graph）ができます。このグラフは、いくつかのサイクルと、そのサイクルに流れ込む木（ρ型の構造）で構成されます。

サイクルに属さないノード（木の部分）

サイクルに属さないノード \(i\) については、\(i\) を先に打ち上げれば \(T_i\) を消滅させ、\(T_i\) を先に打ち上げれば \(i\) は消滅しないので、適切な順番（木の葉から根に向かう順序）で打ち上げれば、木の部分の全ノードを消滅させずに打ち上げられます。

サイクル部分の損失

問題はサイクルです。サイクル \(v_1 \to v_2 \to \cdots \to v_k \to v_1\) を考えます。\(v_1\) を打ち上げると \(v_2\) が消滅、\(v_2\) を打ち上げると \(v_3\) が消滅、…という関係があります。

サイクル内のどのノードから打ち上げても、最初に打ち上げた花火の衝撃波で次の花火が1つ消滅します。残りのノードは消滅した1つを飛ばして順に打ち上げられますが、消滅したノードの衝撃波は発動しないため、それ以降は連鎖的な消滅は起きません。

つまり、各サイクルからちょうど1つのノードが消滅するのが最善です。

結論

木の部分ではノードを失わず、各サイクルでちょうど1つ失うので：

\[\text{答え} = N - (\text{サイクルの個数})\]

具体例

\(N = 4\), \(T = [2, 1, 4, 3]\) の場合、辺は \(1 \to 2, 2 \to 1, 3 \to 4, 4 \to 3\) でサイクルが2つ（\(\{1,2\}\) と \(\{3,4\}\)）あるので、答えは \(4 - 2 = 2\) です。

アルゴリズム

1. 各ノード \(i\) から \(T_i\) へ辺を張った functional graph を構築する。
2. DFS（深さ優先探索）でグラフを走査し、サイクルの個数を数える。
   • 未訪問ノードからパスをたどり、「探索中」のノードに再び到達したらサイクルを1つ検出。
   • 「探索済み」のノードに到達した場合は新たなサイクルではない。
3. 答えとして \(N - (\text{サイクルの個数})\) を出力する。

計算量

• 時間計算量: \(O(N)\)（各ノードを高々定数回訪問）
• 空間計算量: \(O(N)\)（グラフ・訪問状態・パスの記録）

実装のポイント

• functional graph ではサイクル検出が容易です。各ノードから次のノードをたどるだけで、visited 配列に「未訪問(0)」「探索中(1)」「探索済(2)」の3状態を持たせれば、探索中のノードに戻ったときにサイクルと判定できます。

• \(N\) が最大 \(10^6\) と大きいため、再帰DFSではスタックオーバーフローの危険があります。コード中ではイテレーティブに while ループでパスをたどることで回避しています。

• Python では sys.stdin.buffer.read() で高速に入力を読み取るのが重要です。

  ソースコード

import sys
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    T = [int(input_data[i+1]) - 1 for i in range(N)]
    
    # Count cycles in functional graph
    # Each node has out-degree 1
    visited = [0] * N  # 0: unvisited, 1: in progress, 2: done
    num_cycles = 0
    
    for start in range(N):
        if visited[start] != 0:
            continue
        path = []
        node = start
        while visited[node] == 0:
            visited[node] = 1
            path.append(node)
            node = T[node]
        
        if visited[node] == 1:
            # Found a cycle - count it
            # Find where the cycle starts in path
            cycle_start = node
            idx = 0
            while path[idx] != cycle_start:
                idx += 1
            num_cycles += 1
        
        for p in path:
            visited[p] = 2
    
    print(N - num_cycles)

solve()

---

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