记录编号	384129	评测结果	AAAAAAAAAA
题目名称	[NOIP 2015]信息传递	最终得分	100
用户昵称	Hzoi_Hugh	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2017-03-17 13:58:29	内存使用	33.48 MiB

#include<cstdio>
using namespace std;
int n,m[2000001],low[2000001],dfn[2000001],t,stack[2000001],top,num=0x7f7f7f7f,u[200000],p;
bool in[2000001];
void tar(int x)
{
   stack[++top]=x;
   low[x]=dfn[x]=++t;
   in[x]=1;
   if(dfn[m[x]]==0)
   {
     tar(m[x]);
     low[x]=low[x]<low[m[x]]?low[x]:low[m[x]];
   }
   else if(in[m[x]])
     low[x]=low[x]<dfn[m[x]]?low[x]:dfn[m[x]];
   if(low[x]==dfn[x])
   {
     int i;
     p++;
     do
     {
       i=stack[top--];
       in[i]=0;
       u[p]++;
     }while(i!=x);
   }
}
int main()
{
    freopen("2015message.in","r",stdin);
	freopen("2015message.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
     scanf("%d",&m[i]);
    for(int i=1;i<=n;i++)
     if(!dfn[i])
       tar(i);
    for(int i=1;i<=p;i++)
     if(u[i]<num&&u[i]>1)
      num=u[i];
    printf("%d",num);
    //while(1);
    return 0;
}