思路

我们可以把众多同学抽象成一个有向图，节点 $i$ 的后继节点为 $a[i]$。本题就是要找出这个图中的最小环。

我们设 $f[i]$ 表示 $i$ 的编号（或者是第几个被遍历到的）；每遍历一轮新的编号就要在原来的基础上统一加上 $2n$，防止混淆。

我们依次遍历每一个点，如果这个点还没被遍历过，我们就对它进行dfs，假设当前点为 $i$：

• 如果 $i$ 的后继节点已经被遍历过，那么说明存在环或者是第二轮遍历。我们就更新答案，当前环的大小为 $f[i]-f[a[i]]$。
• 如果 $i$ 的后继节点没被遍历过，我们就将它的编号设为 $f[i]+1$。

最后输出最小的答案。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e5+5;
ll n,a[N],f[N],ans=LLONG_MAX,cnt=1;
void dfs(ll x){
    if(f[a[x]]){
        ans=min(ans,f[x]-f[a[x]]+1);
        return;
    }
    f[a[x]]=f[x]+1;
    dfs(a[x]);
}
int main(){
    scanf("%lld",&n);
    for(ll i=1,v;i<=n;i++)
        scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++)
        if(!f[i]){
            f[i]=cnt;
            cnt+=2*n;
            dfs(i);
        }
    printf("%lld",ans);
    return 0;
}