• Source 
    1. /**************************************************************
    2.     Problem: 1529
    3.     User: zrts
    4.     Language: C++
    5.     Result: Accepted
    6.     Time:2316 ms
    7.     Memory:63620 kb
    8. ****************************************************************/
    9.  
    10. #include<cstdio>
    11. #include<cstring>
    12. #include<algorithm>
    13. //by zrt
    14. //problem:
    15. using namespace std;
    16. typedef long long ll;
    17. const double eps(1e-10);
    18. int n;
    19. int H[1000005],X[1000005],P[1000005],tot;
    20. inline void add(int x,int y){
    21.     P[++tot]=y;X[tot]=H[x];H[x]=tot;
    22. }
    23. int tim,low[1000005],stk[1000005],top;
    24. bool instack[1000005];
    25. int cnt;
    26. int belong[1000005];
    27. void tarjan(int x){
    28.     int dfn=low[x]=++tim;
    29.     instack[x]=1;stk[top++]=x;
    30.     for(int i=H[x];i;i=X[i]){
    31.         if(!low[P[i]]) tarjan(P[i]),low[x]=min(low[x],low[P[i]]);
    32.         else if(instack[P[i]]) low[x]=min(low[x],low[P[i]]);
    33.     }
    34.     if(low[x]==dfn){
    35.         cnt++;
    36.         int k;
    37.         do{
    38.             k=stk[--top];
    39.             instack[k]=0;
    40.             belong[k]=cnt;
    41.         }while(k!=x);
    42.     }
    43. }
    44. bool ind[1000005];
    45. int main(){
    46.     #ifdef LOCAL
    47.     freopen("in.txt","r",stdin);
    48.     freopen("out.txt","w",stdout);
    49.     #endif
    50.     scanf("%d",&n);
    51.     for(int i=1,x;i<=n;i++){
    52.         scanf("%d",&x);
    53.         add(x,i);
    54.     }
    55.     for(int i=1;i<=n;i++){
    56.         if(!low[i]) tarjan(i);
    57.     }
    58.     for(int i=1;i<=n;i++){
    59.         for(int j=H[i];j;j=X[j]){
    60.             if(belong[i]!=belong[P[j]]) ind[belong[P[j]]]=1;
    61.         }
    62.     }
    63.     int ot=0;
    64.     for(int i=1;i<=cnt;i++){
    65.         if(!ind[i]) ot++;
    66.     }
    67.     printf("%d\n",ot);
    68.     return 0;
    69. }