概要

花火の衝撃波の対象をグラフの辺と見なしたとき、打ち上げる順番を工夫することで消滅してしまう花火の数を最小化する問題です。グラフ内の「閉路（サイクル）」の数を数えることで答えを導き出します。

考察

1. グラフによるモデル化 花火を「頂点」、衝撃波の対象を「有向辺」としたグラフを考えます。花火 \(i\) から花火 \(T_i\) へ有向辺 \(i \to T_i\) を引きます。すべての花火の対象はちょうど1つなので、各頂点から必ず1本の矢印が出るグラフ（Functional Graph と呼ばれます）になります。

2. 消滅を防ぐ条件 花火 \(i\) を打ち上げると、花火 \(T_i\) が準備中の場合は消滅してしまいます。これを防ぐためには、花火 \(i\) よりも先に花火 \(T_i\) を打ち上げる必要があります。

3. 直線や木の部分の処理 たとえば \(1 \to 2 \to 3\) のような関係であれば、矢印の先にある \(3\) から順に \(3 \to 2 \to 1\) と打ち上げることで、誰も消滅することなくすべてを打ち上げることができます。つまり、閉路になっていない部分はうまく順番を工夫すればすべて打ち上げ可能です。

4. 閉路（サイクル）の処理 しかし、\(1 \to 2 \to 3 \to 1\) のようにぐるぐるとループしている閉路の場合、どこから始めても「最初の1発目」を打ち上げた瞬間に、その対象となる花火が消滅してしまいます。 例えば \(1\) を打ち上げると \(2\) が消滅します。すると残った \(3\) の対象である \(1\) はすでに打ち上げ済みなので、\(3\) は安全に打ち上げられます。 結果として、長さ \(C\) の閉路ではどうしても1つの花火が消滅してしまいますが、残りの \(C-1\) 個は打ち上げることができます。

5. 結論 各頂点から1本の辺が出るグラフは、いくつかの連結成分に分かれ、各連結成分には必ず「1つの閉路」が含まれます。 消滅してしまう花火の数は、この「閉路の数」と完全に一致します。したがって、演出リストに記録される花火の最大数は \(N - (\text{閉路の数})\) となります。

アルゴリズム

閉路の数を数えるために Union-Find（素集合データ構造） を使用します。

1. 初期状態では、各花火をそれぞれ独立したグループ（親が自分自身）とします。
2. 各花火 \(i\) について、辺 \(i \to T_i\) を順に追加していきます。
3. 辺を追加する際、頂点 \(i\) と頂点 \(T_i\) がすでに同じグループに属しているかを Union-Find で確認します。
   • もし同じグループであれば、この辺を繋ぐことで「閉路」が1つ完成したことがわかります。閉路のカウント（cycles）を1増やします。
   • 違うグループであれば、2つのグループを統合します。
4. すべての辺を処理し終えた後、\(N - \text{cycles}\) を出力します。

計算量

• 時間計算量: \(O(N \alpha(N))\) Union-Findの操作はアッカーマン関数の逆関数 \(\alpha(N)\) がかかりますが、これは非常に小さく実質的に定数時間です。全体としてほぼ \(O(N)\) で高速に動作します。
• 空間計算量: \(O(N)\) Union-Findの親を管理する配列 parent に \(O(N)\) のメモリを使用します。

実装のポイント

Pythonで Union-Find の find 関数を再帰関数で実装すると、\(1 \to 2 \to 3 \to \dots \to N\) のような一直線のグラフが与えられた場合に再帰の深さ制限（RecursionError）に引っかかる可能性があります。

提供された正解コードでは、while ループを用いて再帰を使わずに「経路圧縮（Path Compression）」を行っています。これにより、sys.setrecursionlimit 等で上限を変更する手間やエラーの心配がなく、安全かつ高速に動作する工夫が施されています。

ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    
    parent = list(range(N + 1))
    
    def find(i):
        curr = i
        while parent[curr] != curr:
            curr = parent[curr]
        p = i
        while p != curr:
            nxt = parent[p]
            parent[p] = curr
            p = nxt
        return curr

    cycles = 0
    for i in range(1, N + 1):
        u = i
        v = int(data[i])
        
        root_u = find(u)
        root_v = find(v)
        if root_u == root_v:
            cycles += 1
        else:
            parent[root_u] = root_v

    print(N - cycles)

if __name__ == '__main__':
    solve()

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