记录编号	456912	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]信息传递	最终得分	100
用户昵称	REALIZE_BEYOND	是否通过	通过
代码语言	C++	运行时间	0.145 s
提交时间	2017-10-05 21:55:19	内存使用	6.42 MiB

#include<stack>
#include<cstdio>
#include<iostream>
#define maxn 200005
#define maxm 200005

using namespace std;
int n,k=0,head[maxn],dfn[maxn],low[maxn],tim=0,Bcnt=0,instack[maxn],belong[maxn],v[maxn],ans=666666;
stack<int>z;
inline void read(int &x){
	char c;int flag=0;
	while(!isdigit(c=getchar()))
	  if(c=='-') flag=1;
	x=c-'0';
	while(isdigit(c=getchar()))
	  x=x*10+c-'0';
	if(flag) x=-x;
}
struct Edge{
	int to,next;
}e[maxm];
inline void add_edge(int x,int y){
	e[++k].to=y;
	e[k].next=head[x];
	head[x]=k;
}
inline void tarjan(int x){
	int y;
	dfn[x]=low[x]=++tim;
	z.push(x);
	instack[x]=true;
	for(int i=head[x];i;i=e[i].next){
		y=e[i].to;
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[y],low[x]);
		}
		else if(instack[y])
		  low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		Bcnt++;
		do{
			y=z.top();
			z.pop();
			belong[y]=Bcnt;
			instack[y]=false;
			v[Bcnt]++;
		}while(x!=y);
	}
}
int main(){
	freopen("2015message.in","r",stdin);
	freopen("2015message.out","w",stdout);
	ios::sync_with_stdio(false);
	read(n);
	int x;
	for(int i=1;i<=n;i++){
		read(x);
		add_edge(i,x);
	}
	for(int i=1;i<=n;i++)
	  if(!dfn[i])
	    tarjan(i);
//	cout<<Bcnt<<"\n";
//	for(int i=1;i<=n;i++) cout<<dfn[i]<<" "<<low[i]<<"\n";   
//	for(int i=1;i<=Bcnt;i++) cout<<v[i]<<" ";cout<<"\n";
	for(int i=1;i<=Bcnt;i++)
		if(v[i]!=1)
		ans=min(v[i],ans);
	cout<<ans;
	return 0;
}