NOIP2015 提高组 day1T2---信息传递

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;
}