题目描述
每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在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只奶牛要前往的隔间数。
记忆化搜索好题！！！！！！
思路： 递归更新dis数组 表示距离结束的距离
两个记忆化递归 wa了好多小细节
#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define REP(i,N) for(int i=0;i<(N);i++)
#define CLR(A,v) memset(A,v,sizeof A)
#define inf 0x3f3f3f3f
//////////////////////////////////
const int N=+;
int n;
int mp[N];
int vis[N];
int in[N];
int dis[N];
int dfs1(int x,int cnt)
{
dis[x]=cnt;
if(dis[ mp[x] ]){return cnt;}
else return dis[x]=dfs1(mp[x],cnt+);
}
void del(int x)
{
vis[x]=;
if(--in[mp[x]]==)del(mp[x]);
}
int dfs(int x)
{
if(dis[ x ])return dis[x];
else return dis[x]=dfs(mp[x])+;
}
int main()
{
RI(n);
rep(i,,n)RI(mp[i]),in[mp[i]]++; rep(i,,n)
if(!in[i]&&!vis[i])
del(i); rep(i,,n)
if(!dis[i]&&in[i])
dfs1(i,); rep(i,,n)
{
if(dis[i])cout<<dis[i]<<endl;
else
dfs(i),cout<<dis[i]<<endl;
}
return ;
}
细节：
int dfs1(int x,int cnt)
{
vis[x]=;
if(vis[mp[x]]){dis[x]=cnt;return cnt;}//注意 如果这样 写不能漏掉dis[x]=cnt!!!
else return dis[x]=dfs1(mp[x],cnt+);
}