记录编号	473332	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]信息传递	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.164 s
提交时间	2017-11-08 16:23:10	内存使用	2.79 MiB

#include<cstdio>
#include<iostream>
const int maxn=2e5+5;
using namespace std;
struct edge
{
	int fr,to;
	edge *nt;
	edge(){fr=to=0;nt=NULL;}
}*e[maxn];
inline int get();
inline edge *add(int fr,int to);
void dfs(int now,int t);
int n,ans=0x7ffff;
int in[maxn],turn[maxn];
bool jud[maxn];
int main()
{
	freopen("2015message.in","r",stdin);
	freopen("2015message.out","w",stdout);
	n=get();
	for(int i=1;i<=n;i++)
	{
		int to=get();
		e[i]=add(i,to);
		in[to]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(!in[i])dfs(i,1);
		else if(!jud[i])dfs(i,1);
	}
	printf("%d\n",ans);
	return 0;
}
void dfs(int now,int t)
{
	jud[now]=true;
	if(turn[now])
	{
		ans=min(ans,t-turn[now]);
		return;
	}
	turn[now]=t;
	for(edge *i=e[now];i;i=i->nt)
		if(in[i->to])
			in[i->to]--,dfs(i->to,turn[now]+1);
	turn[now]=0;
}
inline edge *add(int fr,int to)
{
	edge *p=new edge();
	p->fr=fr;p->to=to;
	p->nt=e[fr];
	return p;
}
inline int get()
{
	int t=0;char c=getchar(),j=1;
	while(!isdigit(c))
		if(c=='-')j=-1,c=getchar();
		else c=getchar();
	while(isdigit(c))
		t=(t<<3)+(t<<1)+c-'0',
		c=getchar();
	return j*t;
}