题目描述
原题题面
每年万圣节，威斯康星的奶牛们都要打扮一番，出门在农场的N个牛棚里转 悠，来采集糖果.她们每走到一个未曾经过的牛棚，就会采集这个棚里的1颗糖果.
农场不大，所以约翰要想尽法子让奶牛们得到快乐.他给每一个牛棚设置了一个“后继牛 棚”.牛棚i的后继牛棚是next_i 他告诉奶牛们，她们到了一个牛棚之后，只要再往后继牛棚走去， 就可以搜集到很多糖果.事实上这是一种有点欺骗意味的手段，来节约他的糖果.
第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．
第i只奶牛从牛棚i开始她的旅程．请你计算，每一只奶牛可以采集到多少糖果．
【AC代码】:
#include <bits/stdc++.h>
#define M(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f
#define MOD 10000007
using namespace std;inline void read(int &x){
char ch=getchar(),c=ch;x=0;while(ch<'0' || ch>'9'){
c=ch;ch=getchar();}while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}if(c=='-')x=-x;
}const int maxn=100005;int n,i,k,cnt=0;
int next[maxn],col[maxn],dfn[maxn],dfn2[maxn],cow[maxn];int main(){
read(n);for(i=1;i<=n;i++)read(next[i]);for(k=1;k<=n;k++){
cnt=0;for(i=k;;i=next[i],cnt++){
if(!col[i]){
col[i]=k;dfn[i]=cnt;}elseif(col[i]==k){
cow[k]=cnt-dfn[i];dfn2[k]=dfn[i];printf("%d\n",cnt);break;}else{
cow[k]=cow[col[i]];dfn2[k]=cnt+max(dfn2[col[i]]-dfn[i],0);printf("%d\n",dfn2[k]+cow[k]);break;}}}
}