记录编号	207988	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]信息传递	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2015-11-14 21:47:27	内存使用	3.88 MiB

#include<stack>
#include<cstdio>

using namespace std;

int siz[200010];
bool ins[200010];
int bl[200010];
int n,T[200010],tot,cnt;
int dfn[200010],low[200010],Ans;
stack<int>s;

int Min(int a,int b){return a<b?a:b;}

void tarjan(int x)
{
	dfn[x]=low[x]=++tot;s.push(x);ins[x]=1;
	if(!dfn[T[x]]){
		tarjan(T[x]);
		low[x]=Min(low[x],low[T[x]]);
	}
	else if(ins[T[x]])
	    low[x]=Min(low[x],dfn[T[x]]);
	if(dfn[x]==low[x]){
		int y;cnt++;
		do{
			y=s.top();
			s.pop();
			ins[y]=0;
			siz[cnt]++;
			bl[y]=cnt;
		}while(y!=x);
	}
}

int main()
{
	freopen("2015message.in","r",stdin);
	freopen("2015message.out","w",stdout);
	scanf("%d",&n);Ans=0x2fffffff;
	if(n==1){printf("1");return 0;}
	for(int i=1;i<=n;i++)scanf("%d",&T[i]);
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=cnt;i++){
		if(siz[i]!=1)Ans=Min(Ans,siz[i]);
	}printf("%d",Ans);
	fclose(stdin);fclose(stdout);
	return 0;
}