题目描述

将 1∼n 按顺序排成一排，构成一个数列。

数字 i 刚好位于位置 i。

再给定一个长度为 n 的位置序列 p1,p2,…,pn，它是 1∼n 的一种排列。

接下来，我们会重复不断地对数列进行如下操作：

重新排列数列中每个数的位置，将位于位置 i 的数移动至位置 pi。（如果 i=pi 则该数仍移动至位置 i）。
每次操作开始时，所有数的移动同时进行，操作结束后，数列将变为一个新的 1∼n 的排列。
例如，当 n=6 并且 p=[4,6,1,3,5,2] 时，第一次操作后，数字 1 将移动至位置 4，数字 2 将移动至位置 6，以此类推；第二次操作后，数字 1 将移动至位置 3，数字 2 将移动至位置 2，以此类推。

你的任务是确定从 1 到 n 的每个数字 i，经过多少次操作后，第一次重新回到位置 i。

例如，考虑 p=[5,1,2,4,3]，数字 1 的移动轨迹如下：

第一次操作后，到达位置 5。
第二次操作后，到达位置 3。
第三次操作后，到达位置 2。
第四次操作后，回到位置 1。
所以，经过四次操作后，数字 1 第一次回到位置 1。

值得一提的是，数字 4 经过一次操作后就回到了位置 4.

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 n。

第二行包含 n 个整数 p1,…,pn。

输出格式

每组数据输出一行结果，包含 n 个整数，其中第 i 个整数表示数字 i 第一次回到位置 i 所经过的操作次数。

整数之间用单个空格隔开。

数据范围

对于 30% 的数据，1≤T≤10，1≤n≤10。
对于 100% 的数据，1≤T≤1000，1≤n≤2×105，1≤pi≤n。
保证 p1∼pn 是 1∼n 的一种排列。
保证 ∑n≤2×105（一个输入中的 T 个 n 相加之和不超过 2×105）。

样例

输入样例：

6
5
1 2 3 4 5
3
2 3 1
6
4 6 2 1 5 3
1
1
4
3 4 1 2
5
5 1 2 4 3

输出样例：

1 1 1 1 1
3 3 3
2 3 3 2 1 3
1
2 2 2 2
4 4 4 1 4

算法1

(并查集求连通块个数)

参考文献

https://www.acwing.com/activity/content/code/content/1300090/

https://www.acwing.com/problem/content/839/

C++ 代码

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

using namespace std;

const int N = 200010;

int n,T;
int p[N],s[N];

int find(int x){  //并查集+路径压缩
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){  //初始化
            p[i]=i;
            s[i]=1;
        }
        for(int i=1;i<=n;i++){
            int j;
            cin>>j;
            if(find(i)!=find(j)){
                s[find(j)]+=s[find(i)];
                p[find(i)]=find(j);
            }
        }
        for(int i=1;i<=n;i++){
            printf("%d ",s[find(i)]);
        }
        puts(" ");
    }
    return 0;
}