E - Transition Game

发布时间 2023-04-03 22:18:22作者: lightsong

E - Transition Game

https://atcoder.jp/contests/abc296/tasks/abc296_e

思路

 

 

 

 

Code

https://atcoder.jp/contests/abc296/submissions/40262511

#include <bits/stdc++.h>
using namespace std;
map<int,vector<int> >mp;
int deg[200006];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int j;
        cin>>j;
        mp[i].push_back(j);
        deg[j]++;
    }
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(deg[i]==0){
            q.push(i);
        }
    }
    int ans=n;
    while(!q.empty()){
        int nm=q.front();
        q.pop();
        ans--;
        for(int i=0;i<mp[nm].size();i++){
            deg[mp[nm][i]]--;
            if(deg[mp[nm][i]]==0){
                q.push(mp[nm][i]);
            }
        }
    }
    cout<<ans<<endl;
}