题目链接：https://www.luogu.org/problemnew/show/P2921
这道题在洛谷上显示的难度（提高+/省选-）对于我来说还真不小。但事实上，思路还是很容易有的。因为每个结点入度为零，所以只有两种情况：环和环上加链（和信息传递那道题很像https://www.cnblogs.com/Mr94Kevin/p/9521585.html）。只要一个点在环上，那么答案就是环的长度；如果是在链上，那么答案就是点到环的距离加上环的长度。同样，参照信息传递那道题的做法，我们可以先删链，再搜环。总之一定要找对判断环的方法，不能错误的认为链环上的点只要入度不为1就是链和环的交点，更不能因此浪费大量时间！！！
1 #include<cstdio> 2 #include<cctype> 3 inline int get_num() { //读入优化 4 int num; 5 char c; 6 while((c=getchar())==‘\n‘||c==‘ ‘||c==‘\r‘); 7 num=c-‘0‘; 8 while(isdigit(c=getchar())) num=num*10+c-‘0‘; 9 return num; 10 } 11 void put_num(int i) { //输出优化 12 if(i>9) put_num(i/10); 13 putchar(i%10+‘0‘); 14 } 15 const int maxn=1e5+5; 16 int n,next[maxn],vis[maxn],d[maxn],ans[maxn],cnt; 17 int dfs1(int i) { //处理环 18 int j=next[i]; 19 if(vis[j]) return ans[i]=cnt+1-vis[j]; //得到环的大小 20 else { 21 vis[j]=++cnt; 22 return ans[i]=dfs1(j); //同一个环上的结点答案均为环的大小 23 } 24 } 25 int dfs2(int i) { //处理链环 26 if(ans[i]) return ans[i]; //类似记忆化搜索 27 int j=next[i]; 28 return ans[i]=dfs2(j)+1; 29 } 30 int main() { 31 n=get_num(); 32 for(int i=1;i<=n;++i) next[i]=get_num(),++d[next[i]]; 33 for(int i=1;i<=n;++i) //删边，找环 34 if(!d[i]) { 35 d[i]=-1; 36 for(int j=next[i];;j=next[j]) { 37 if(--d[j]) break; 38 else d[j]=-1; 39 } 40 } 41 for(int i=1;i<=n;++i) //先处理环 42 if(!vis[i]&&d[i]!=-1) { 43 cnt=1; 44 dfs1(i); 45 } 46 for(int i=1;i<=n;++i) //再处理环上的链 47 if(!vis[i]) dfs2(i); 48 for(int i=1;i<=n;++i) { 49 if(i!=1) putchar(‘\n‘); 50 put_num(ans[i]); 51 } 52 return 0; 53 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9532810.html
