E - Transition Game Editorial by evima
楽な実装方針問われている内容をグラフ理論の用語を使って簡潔に述べると次の通りです。
- 全頂点の出次数が \(1\) であるような \(N\) 頂点の有向グラフ (functional graph) がある。頂点 \(i\) からは頂点 \(A_i\) への辺がある。サイクルに含まれる頂点の個数を求めよ。
これには強連結成分分解を用いるのが手っ取り早いでしょう。
実装例(C++、AtCoder Library を利用)
#include <iostream>
#include <atcoder/scc>
using namespace std;
using namespace atcoder;
int main(){
int N;
cin >> N;
scc_graph g(N);
int ans = 0;
for(int i = 0; i < N; ++i){
int A;
cin >> A, --A;
g.add_edge(i, A);
if(i == A){
++ans;
}
}
for(auto c: g.scc()){
if(c.size() >= 2){
ans += c.size();
}
}
cout << ans << endl;
}
posted:
last update: