結論から述べると、次のように求解できます。

• \(N\) 個の頂点 \(1,2,\dots,N\) と \(i \rightarrow T_i\) 間に \(N\) 本の有向辺を張った有向グラフ \(D\) を考えます。
• このとき、答えは \(N-\) ( \(D\) の (辺の向きを無視した) 連結成分数 ) です。

以下の事実を示すことで、上記の解法を証明できます。

• (辺の向きを無視した) 連結成分ごとに \(1\) 発の花火の暴発は避けられず、逆に必ず \(1\) 発の暴発で済ませる方法が存在する。

\(N\) 個の頂点 \(1,2,\dots,N\) と \(i \rightarrow T_i\) 間に \(N\) 本の有向辺を張った有向グラフ \(D\) を考えます。

各連結成分は Functional Graph と呼ばれるもので、以下の良い性質があります。 参考

• 各連結成分にはちょうど \(1\) つの閉路があり、そこにいくつか有向木が繋がった形になっている。

制約より \(i \neq T_i\) なので、最初に打ち上げた花火に着目すると連結成分ごとに \(1\) 発の暴発は避けられないことがわかります。
そこで、最初に閉路の中に含まれる花火 \(i\) を打ち上げることを考えます。
すると、以下の手順で花火 \(T_i\) を除いて閉路の中の花火は暴発させずに打ち上げることができます。

• \(u=i\) から始める。
• 閉路の中に \(T_v = u\) なる花火 \(v\) が存在する限り、 \(v\) を打ち上げた後 \(u\) を \(v\) に置き換えることを繰り返す。

こうして閉路の中で \(1\) 発のみ花火を暴発させて打ち上げることができ、残りの花火も閉路に繋がっていたものから順に打ち上げることで暴発を回避して打ち上げることができます。

以上で冒頭の事実の証明が完了しました。

本解法の時間計算量は \(O(N)\) です(実装例では Union-Find を利用しているため、実際は \(O(N \alpha(N))\) です)。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/dsu>

using namespace std;
using namespace atcoder;

int main(){
  int N;
  cin >> N;
  dsu d(N+1);
  int res=0;
  for(int i=1;i<=N;i++){
    int T;
    cin >> T;
    if(!d.same(i,T)){
      res++;
      d.merge(i,T);
    }
  }
  cout << res << "\n";
  return 0;
}