题目就是在找环的长度,可以用dfs寻找环,找到环之后记录每个点的环长度.
时间复杂度$O(n)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 3e5 + 10;
int a[N];
int circle[N];//circle[i]表示环的长度
int rec(int x,int t,int ori){
    if(x == ori){//找到自己的时候说明遍历了一遍环,可以返回
        circle[ori] = t + 1; //记录环长度
        return t + 1;
    }
    else {
        circle[x] = rec(a[x],t+1,ori);
        return circle[x];
        //类似于并查集的路径压缩,这里在递归回溯的时候把环上的所有点的环长更新
    }
}
//事实上这个暴搜特别像并查集的find函数


int main()
{
    int T;cin>>T;
    while(T --){
        int n;scanf("%d",&n);
        memset(a,0,sizeof a);
        memset(circle,0,sizeof circle);
        for(int i = 1 ; i <= n; ++ i){
            scanf("%d",&a[i]);
        }
        for(int i = 1; i <= n; ++ i){
            if(!circle[a[i]]){//如果环长未确定则需要搜索,否则跳过
                rec(a[a[i]],0,a[i]);//cout<<"F";
            }
            printf("%d ",circle[a[i]]);
        }
        puts("");

    }

    return 0;
}