在农场万圣节Trick or Treat on the Farm

Description

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。

由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。

FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。

在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。

Input

第1行整数n。

第2行到n+1行每行包含一个整数 next_i 。

n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。

Examples

Input

Output

正确解法：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
           6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               
                11 using namespace std;12 typedef long long ll;13 const int N=100000+100;14 int Link[N],len=0,bok[N];15 int n,yy,ans[N],que[N];16 struct student17 {18 int y,next;19 }e[N];20 void insert(int xx,int yy)21 {22 e[++len].next=Link[xx];23 Link[xx]=len;24 e[len].y=yy;25 }26 int bfs(int x)27 {28 memset(bok,0,sizeof(bok));29 int head=1,tail=2;30 ans[x]++;31 que[head]=x;32 bok[x]=1;33 while(head

暴力40分的code

转载于:https://www.cnblogs.com/Kaike/p/10461544.html

你可能感兴趣的文章

在农场万圣节Trick or Treat on the Farm

Description

Input

output

Examples

Input

Output

正确解法：