Description

每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N(1≤N≤100000)个牛棚里转悠，来采集糖果．她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果． 农场不大，所以约翰要想尽法子让奶牛们得到快乐．他给每一个牛棚设置了一个“后继牛棚”．牛棚i的后继牛棚是Xi．他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去，就可以搜集到很多糖果．事实上这是一种有点欺骗意味的手段，来节约他的糖果．  第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．

Input

    第1行输入N，之后一行一个整数表示牛棚i的后继牛棚Xi，共N行．

Output

 

    共N行，一行一个整数表示一只奶牛可以采集的糖果数量．

Sample Input

4 //有四个点

1 //1有一条边指向1

3 //2有一条边指向3

2 //3有一条边指向2

3

INPUT DETAILS:

Four stalls.

* Stall 1 directs the cow back to stall 1.

* Stall 2 directs the cow to stall 3

* Stall 3 directs the cow to stall 2

* Stall 4 directs the cow to stall 3

Sample Output

1

2

2

3

————————————————————————

这道题就是求一个点到他指向的环的距离+环的大小

所以拓扑排序求一下环 然后根据拓扑的队列倒着求一波答案

#include
       
        #include
        
         #include
         
          using namespace std;const int M=150007;int read(){    int ans=0,f=1,c=getchar();    while(c<'0'||c>'9'){
     if(c=='-') f=-1; c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}    return ans*f;}int n,to[M],in[M],stk[M],top,f[M];int head,tail,q[M];int main(){    n=read();    for(int i=1;i<=n;i++) to[i]=read(),in[to[i]]++;    for(int i=1;i<=n;i++) if(!in[i]) q[tail++]=i;    while(head<=tail){        int x=q[head++],now=to[x];        in[now]--;        if(!in[now]) q[tail++]=now;    }    for(int i=1;i<=n;i++)if(in[i]){        int now=i,h=1;        stk[top=1]=i; in[i]=0;        while(1){            now=to[now];            if(now==i) break;            h++; in[now]=0; stk[++top]=now;        }        while(top) f[stk[top]]=h,top--;    }    while(tail>0) tail--,f[q[tail]]=f[to[q[tail]]]+1;    for(int i=1;i<=n;i++) printf("%d\n",f[i]);    return 0;}