记录编号	338583	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]信息传递	最终得分	100
用户昵称	Zwoi_只会打表抄代码的蒟蒻	是否通过	通过
代码语言	C	运行时间	0.387 s
提交时间	2016-11-05 12:00:11	内存使用	3.69 MiB

#include <stdio.h>
int tell[200010],book[200010],start[200010],tail,a[200010],x,min,pre,t,j,i,n,last[200010];
int main()
{
	freopen("2015message.in","r",stdin);
	freopen("2015message.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&tell[i]);
		book[tell[i]]=1;
	}
	tail=0;
	min=0x7f7f7f7f;
	for(i=1;i<=n;i++)
		if(!book[i])
		{
			tail++;
			start[tail]=i;
		}
	memset(book,0,sizeof(book));
	for(i=1;i<=tail;i++)
	{
		t=tell[start[i]];
		a[start[i]]=x=1;
		while(book[t]==0)
		{
			book[t]=i;
			x++;
			a[t]=pre=x;
			t=tell[t];
		}
		if(pre-a[t]+1<min&&book[t]==i)
			min=pre-a[t]+1;
	}
	j=0;
	for(i=1;i<=n;i++)
	{
		if(a[i]==0)
			last[++j]=i;
	}
	memset(book,0,sizeof(book));
	for(i=1;i<=j;i++)
	{
		if(!book[last[i]])
		{
			book[last[i]]=1;
			t=tell[last[i]];
			x=1;
			while(!book[t])
			{
				book[t]=1;
				x++;
				t=tell[t];
			}
			if(x<min)
				min=x;
		}
	}
	printf("%d",min);
	return 0;
}