记录编号	221158	评测结果	AAAAAAAAAA
题目名称	2105.[NOIP 2015]信息传递	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.144 s
提交时间	2016-01-22 09:44:07	内存使用	3.53 MiB

#include<cstdio>
#include<cstring>
const int maxn = 200005;
int ans=1<<20,n,t=0,dfn[maxn],low[maxn],to[maxn],m=0,s[maxn],top=0;
bool instack[maxn];
void tarjan(int a){
	low[a]=dfn[a]=++t;
	s[top++]=a;
	instack[a]=true;
	if(!dfn[to[a]]){
		tarjan(to[a]);
		if(low[to[a]]<low[a])low[a]=low[to[a]];
	}else if(instack[to[a]]&&dfn[to[a]]<low[a])low[a]=dfn[to[a]];
	if(dfn[a]==low[a]){
		int len = 0,j;
		do{
			j = s[--top];
			len++;
		}while(j!=a);
		if(len>1&&len<ans)ans = len;	
	}
}
int main(){
	freopen("2015message.in","r",stdin);
	freopen("2015message.out","w",stdout);
	scanf("%d",&n);
	memset(dfn,0,sizeof(dfn));
	for(int i = 1;i<=n;++i)scanf("%d",to+i);
	for(int i = 1;i<=n;++i)if(!dfn[i])tarjan(i);
	printf("%d\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}