记录编号	394771	评测结果	AAAAAAAAAE
题目名称	[NOIP 2015]信息传递	最终得分	90
用户昵称	WildRage	是否通过	未通过
代码语言	C++	运行时间	0.508 s
提交时间	2017-04-14 14:31:22	内存使用	4.51 MiB

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstring>
#include<cstdio>
#include<stack>
using namespace std;
const int N=200005;
struct edge{
	int END,next;
}v[N];
int first[N],p=1;
int ans=0x7fffffff;
int n,dindex;
stack<int> st;
int dfsn[N],low[N];
bool instack[N],flag[N];
void add(int a,int b){
	v[p].END=b;
	v[p].next=first[a];
	first[a]=p++;
}
void tarjan(int x){
	dfsn[x]=low[x]=dindex++;
	st.push(x);
	instack[x]=1;
	if(!flag[v[first[x]].END]){
		for(int i=first[x];i!=-1;i=v[i].next){
			if(!dfsn[v[i].END]){
				tarjan(v[i].END);
				low[x]=min(low[x],low[v[i].END]);
			}
			else if(instack[v[i].END]){
				low[x]=min(low[x],dfsn[v[i].END]);
			}
		}
		flag[x]=1;
	}
	if(dfsn[x]==low[x]){
		int size=0;
		do{
			x=st.top();
			st.pop();
			instack[x]=0;
			size++;
		}while(dfsn[x]!=low[x]);
		if(size>1){
			ans=min(ans,size);
		}
	}
}
int main()
{
	freopen("2015message.in","r",stdin);
	freopen("2015message.out","w",stdout);
	memset(first,-1,sizeof(first));
	cin>>n;
	int s;
	dindex=1;
	for(int i=1;i<=n;i++){
		cin>>s;
		add(i,s);
	}
	for(int i=1;i<=n;i++){
		if(!dfsn[i]){
			tarjan(i);
		}
	}
	cout<<ans<<endl;
}