题目描述
每年，在威斯康星州，奶牛们都会穿上衣服，收集农夫约翰在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=100000+5; 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+1); } void del(int x) {vis[x]=1;if(--in[mp[x]]==0)del(mp[x]); } int dfs(int x) {if(dis[ x ])return dis[x];else return dis[x]=dfs(mp[x])+1; } int main() {RI(n);rep(i,1,n)RI(mp[i]),in[mp[i]]++;rep(i,1,n)if(!in[i]&&!vis[i])del(i);rep(i,1,n)if(!dis[i]&&in[i])dfs1(i,1);rep(i,1,n){if(dis[i])cout<<dis[i]<<endl;elsedfs(i),cout<<dis[i]<<endl;}return 0; }
细节：
int dfs1(int x,int cnt) {vis[x]=1;if(vis[mp[x]]){dis[x]=cnt;return cnt;}//注意 如果这样 写不能漏掉dis[x]=cnt!!!else return dis[x]=dfs1(mp[x],cnt+1); }