信息传递--NOIP2015 day1 T2

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 int n,fa[200001],x[200001],ru[200001],g[200001];
 8 bool w[200001];
 9 
10 int getint()
11 {
12     int w=0,q=0;
13     char c=getchar();
14     while ((c>‘9‘||c<‘0‘)&&c!=‘-‘)
15         c=getchar();
16     if (c==‘-‘) q=1,c=getchar();
17     while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar();
18     return q?-w:w;
19 }
20 
21 void shan(int k)
22 {
23     w[k]=1;
24     ru[fa[k]]--;
25     if(ru[fa[k]]==0)
26         shan(fa[k]);
27 }
28 
29 int main()
30 {
31     n=getint();
32     for (int i=1; i<=n; i++)
33         fa[i]=getint(),ru[fa[i]]++;
34     for (int i=1; i<=n; i++)
35         if(ru[i]==0&&!w[i])
36             shan(i);
37     for (int i=1; i<=n; i++)
38         if(!w[i])
39         {
40             x[1]=fa[i];
41             int y=fa[i],ans=1;
42             while (i!=y) w[y]=1,y=fa[y],x[++ans]=y;
43             for (int j=1; j<=ans; j++)
44                 g[x[j]]=ans;
45         }
46     
47     int ans=0x7fffffff;
48     for (int i=1;i<=n;i++)
49         if(!w[i])
50             ans=min(ans,g[i]);
51     printf("%d",ans);
52 }