题解 | #114514#

就是dfs一遍就行了，找到每一个环。给每一个数赋值一个x，但是如果是这样一个环4->1->2->3->2,一开始遍历了1到2就结束，没有经过4，但是遍历4的时候，因为st[1]=true就结束了,导致w[4]+1-w[1]的答案，是不允许的，况且没有必要走下去了，一开始从遍历的时候就已经找到环了，为避免这种问题，每次遍历x+=n;

#include<bits/stdc++.h>
using namespace std;
int t[200005],w[200005];
long long x=1,ans=0x3f3f3f3f;
bool st[200005];
void dfs(int u){
    if(!st[u]){
        w[u]=x++;
        st[u]=true;
        dfs(t[u]);
    }
    else{
        ans=min(x-w[u],ans);
    }
}
int main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i];
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            dfs(i);
            x+=n;
        }
    }
    cout<<ans;
}