传送门 题意比较明显了，直接说怎么搞。 可以发现每个点的出度都是1，用tarjan缩点后，每一个强连通分量一定是一个环。 如果它本身在一个环里，那么答案就是环的长度。 如果不是在一个环里，那么一定是在链上。沿着链一直走，走到环为止。那么答案就是走过链的长度加上环的长度。 dfs写的话需要一下特判环为1的情况。
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std; void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); } typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; const int N=100010,M=200020; int n,m; int ne[N]; int dfn[N],low[N],id[N],tot,cnt; int stk[N],top; int se[N]; bool in[N]; int ans[N]; void init() { tot=top=cnt=0; for(int i=1;i<=n;i++) { in[i]=false; dfn[i]=low[i]=id[i]=0; se[i]=0; } } void tarjan(int u) { dfn[u]=low[u]=++tot; in[u]=true; stk[++top]=u; int j=ne[u]; if(!dfn[j]) { tarjan(j); low[u]=min(low[u],low[j]); } else if(in[j]) low[u]=min(low[u],dfn[j]); if(dfn[u]==low[u]) { int y; ++cnt; do { y=stk[top--]; in[y]=false; id[y]=cnt; se[cnt]++; }while(y!=u); } } void dfs(int uu,int u,int sum) { if(ans[u]!=0) { ans[uu]=ans[u]+sum-1; return; } else dfs(uu,ne[u],sum+1); } int main() { // ios::sync_with_stdio(false); // cin.tie(0); scanf("%d",&n); init(); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); if(i==x) ans[i]=1; ne[i]=x; } for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i); for(int i=1;i<=n;i++) if(se[id[i]]>1) ans[i]=se[id[i]]; for(int i=1;i<=n;i++) if(ans[i]==0) dfs(i,i,1); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; } /* */