在农场万圣节

在农场万圣节

在农场万圣节

题目描述:

每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在N(1<=N<=100，000)个牛棚隔间中留下的糖果，以此来庆祝美国秋天的万圣节。
由于牛棚不太大，FJ通过指定奶牛必须遵循的穿越路线来确保奶牛的乐趣。为了实现这个让奶牛在牛棚里来回穿梭的方案，FJ在第i号隔间上张贴了一个“下一个隔间”Next_i(1<=Next_i<=N)，告诉奶牛要去的下一个隔间；这样，为了收集它们的糖果，奶牛就会在牛棚里来回穿梭了。
FJ命令奶牛i应该从i号隔间开始收集糖果。如果一只奶牛回到某一个她已经去过的隔间，她就会停止收集糖果。
在被迫停止收集糖果之前，计算一下每头奶牛要前往的隔间数（包含起点）。
输入格式
第1行 整数n。
第2行到n+1行 每行包含一个整数 next_i 。
输出格式
n行，第i行包含一个整数，表示第i只奶牛要前往的隔间数。
样例解释
有4个隔间
隔间1要求牛到隔间1
隔间2要求牛到隔间3
隔间3要求牛到隔间2
隔间4要求牛到隔间3
牛1，从1号隔间出发，总共访问1个隔间；
牛2，从2号隔间出发，然后到三号隔间，然后到2号隔间，终止，总共访问2个隔间；
牛3，从3号隔间出发，然后到2号隔间，然后到3号隔间，终止，总共访问2个隔间；
牛4，从4号隔间出发，然后到3号隔间，然后到2号隔间，然后到3号隔间，终止，总共访问3个隔间。
翻译提供者：吃葡萄吐糖
输入输出样例 输入 #1
4
1
3
2
3
输出 #1
1
2
2
3
这道题和信息传递很像，通过指定路径一直走，直到走到之前所走过的房间就停下。这说明了必定形成了环，而回到了环的起点。所以，这道题就可以先用一个数组d记录路径，走的步数一直相加，直到走到已经走过的房间，用现在所走的步数-之前d所记录的步数即为环的大小。而每个房间路径指定，就可以记录下每个房间要结束一共要走的步数。
C++代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int d[100001];
int visit[100001];
int s[100001];
int h[100001]; //记录到达这个房间的糖果数 
int flag;
int dfs(int u, int now)
{if(h[u])return h[u];if(visit[u] == true){h[u] = now - s[u];  flag = u; return h[u]; //返回环的大小 }visit[u] = true;s[u] = now;dfs(d[u],now + 1);if(flag != 0) {//在环之内全部设置环的大小 if(flag != u)h[u] = h[flag];elseflag = 0; //否则到了出环节点设置flag为0 }elseh[u] = h[d[u]] + 1;return h[u];
}
int main()
{int n;memset(visit,false,sizeof(visit));cin >> n;for(int i = 1; i <= n; i ++){scanf("%d",&d[i]);} for(int i = 1; i <= n; i ++)printf("%dn",dfs(i,1));return 0;
}