传送门
题意比较明显了，直接说怎么搞。
可以发现每个点的出度都是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;
}
/**/