サイクルに到達出来る頂点の個数を求める． そうでない，無駄な頂点を省いていく． 具体的にサイクルを求めたりする必要はなく， 出次数が 1以上の頂点だけ通り続ければサイクルになる． 出次数が 0の頂点 \(v\) に到達しても，サイクルには到達できないので， \(v\) に来るメリットはない． よって，\(v\) と \(v\) に向かう辺は取り除いてよい． このとき，出次数も更新する．
これを繰り返していくと， 頂点と辺を取り除けない状態になる． この時点では，残った全ての頂点は出次数が 1以上なので， 遷移を無限に繰り返すことができる．
Key word: 強連結成分(Strongly connected component) 分解
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,m;
cin >> n >> m;
vvll to(n), from(n);
vll out(n);
rep(i,m){
ll a, b; cin >> a >> b;
--a, --b;
// to[a].push_back(b);
from[b].push_back(a);
out[a]++;
}
queue<ll> que;
rep(i,n){
if(out[i] == 0) que.push(i);
}
while(que.size()){
ll cu = que.front(); que.pop();
for(auto ne: from[cu]){
out[ne]--;
if(out[ne] == 0) que.push(ne);
}
}
ll ans = 0;
rep(i,n) if(out[i]) ans++;
cout << ans << endl;
return 0;
}
