题解 P2921 【[USACO08DEC]在农场万圣节Trick or Treat on the Farm】

其实这道题不需要tarjan，不需要分类讨论，只需要记一下时间戳、环的周长即可.

先用dfs1预处理各个环的周长（包括自环），并把周长的值d标记在整个环上。再用dfs2遍历路线，待到d值为正时，直接返回搜索深度+d.

具体细节看代码（核心部分不超20行）

#include <bits/stdc++.h>
#define inf 5201314
using namespace std;
const int N=3e5+10;
int n,to[N],d[N],dfn[N];
void dfs1(int a,int t){
   if(d[a]||dfn[a]>=inf) return; //避免第三次遍历环，同时避免给环外的节点错误赋d值 
   if(dfn[a]&&dfn[a]<inf) d[a]=t-dfn[a];//第二次遍历环即可利用时间戳之差计算环的周长 
   else dfn[a]=t;
   dfs1(to[a],t+1);
   dfn[a]=inf; //遍历完成后，给路径赋一个极大值，标记此环已经来过
}
int dfs2(int a){
   if(d[a]) return d[a];
   return d[a]=dfs2(to[a])+1;//路径压缩，节省大量时间 
}
int main(){
   cin>>n;
   for(int i=1;i<=n;i++) cin>>to[i];
   for(int i=1;i<=n;i++){
      if(dfn[i]) continue;//说明路径已走过，节省大量时间  
      dfs1(i,1);
   }
   for(int i=1;i<=n;i++) cout<<dfs2(i)<<endl;
   return 0;
}