记录编号 318267 评测结果 AAAAAAAAAA
题目名称 [NOIP 2015]信息传递 最终得分 100
用户昵称 GravatarLOSER 是否通过 通过
代码语言 C++ 运行时间 0.162 s
提交时间 2016-10-09 07:40:26 内存使用 2.25 MiB
显示代码纯文本
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=200010;
struct Edge{int to,next;}e[maxn];
int len,head[maxn];
void Insert(int x,int y){
	e[++len].to=y;
	e[len].next=head[x];
	head[x]=len;
}
int Dfn[maxn],low[maxn],Time;
int Color[maxn],sum[maxn];
#define MIN(a,b) (a<b?a:b)
void Dfs(int x){	
	low[x]=Dfn[x]=++Time;
	Color[x]=-Time;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].to;
		if(Color[y]==0){
			Dfs(y);
			if(low[x]>=low[y]){
				low[x]=low[y];
				sum[low[x]]++;
			}
		}
		else if(Color[y]<0){
			if(low[x]>Dfn[y]){
				low[x]=Dfn[y];
				sum[low[x]]++;	
			}
		}
	}
	Color[x]=Time;
}
int MY(){
	freopen("2015message.in","r",stdin); freopen("2015message.out","w",stdout);
	int n;scanf("%d",&n);
	int x;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		Insert(i,x);
	}
	for(int i=1;i<=n;i++)if(!Dfn[i])Dfs(i);
	int ans=0x7f7f7f7f;
	for(int i=1;i<=n;i++){
		if(sum[low[i]]<=1)continue;
		ans=MIN(ans,sum[low[i]]);
	}
	printf("%d\n",ans);
	return 0;
	
}int YOU=MY();
int main(){;}