NOIP2015 提高組 day1 T2
題解:
顯然這是一個查找最小環的問題,直接暴力 搜也能過,隻不過需要一個限制 搜尋次數 !!!
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>edge[200005];
int vis[200005];
int f[200005];
int ans=0x3f3f3f;
void dfs(int x,int deep){
if(deep>=ans){
return;
}
if(!vis[x]){
vis[x]=deep;
}
else{
ans=min(ans,deep-vis[x]);
return;
}
for(int i=0;i<edge[x].size();i++){
if(edge[edge[x][i]].size())
dfs(edge[x][i],deep+1);
}
}
int main(){
scanf("%d",&n);
bool flag=false;
for(int i=1;i<=n;i++){
int a;
scanf("%d",&a);
edge[i].push_back(a);
if(i==a){
flag=1;
}
f[a]++;
}
if(flag){
printf("1");
return 0;
}
for(int i=1;i<=min(500,n);i++){
if(f[i]&&edge[i].size()){
memset(vis,0,sizeof(vis));
dfs(i,1);
}
}
printf("%d",ans);
return 0;
}