AtCoder Beginner Contest 296 E - Transition Game

客官°小女子只卖身不卖艺 2024-03-24 13:36 63阅读 0赞

[E - Transition Game (atcoder.jp)][E - Transition Game _atcoder.jp]

题意：

![7874049e4e0d4ca2a59acdbd7d466a53.png][]

思路：

![bcbed6544a324fc7bfa1268c1c2fb51b.png][]

这里的等价怎么考虑呢

如果点i在环内，那么一定存在一个k，使得他这么多的起点，存在一个起点使得从这个起点开始走k步能到达点i

这个k值是可以设置的，我们只需把k值设成（起点和终点的距离）%（环的长度）即可

所以就是去判环，有环的话就是赢

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    const int mxe=5e4+10;
    const int mod=1e9+7;
    const int Inf=2e18;
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    queue<int> q;
    int n,tot=0;
    int a[mxn],in[mxn],head[mxn];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
        }
    }
    void topsort(){
        for(int i=1;i<=n;i++){
            if(!in[i]) q.push(i);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int i=head[u];~i;i=edge[i].next){
                in[edge[i].to]--;
                if(!in[edge[i].to]) q.push(edge[i].to);
            }
        }
    }
    void solve(){
        cin>>n;
        G_init();
        for(int i=1;i<=n;i++){
            cin>>a[i];
            add(i,a[i]);
            in[a[i]]++;
        }
        topsort();
        int ans=0;
        for(int i=1;i<=n;i++){
            if(in[i]) ans++;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[E - Transition Game _atcoder.jp]: https://atcoder.jp/contests/abc296/tasks/abc296_e
[7874049e4e0d4ca2a59acdbd7d466a53.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4a26438958ab4567abe0ee5b72a8f5bd.png
[bcbed6544a324fc7bfa1268c1c2fb51b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9146d8facae14375b41e257ed82c110e.png