题目描述

将 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

(并查集) $O(nlog(n))$

while迭代模拟TLE了。

把这些数字看成图中一个个结点，每个结点回到自己的step，就是所在的环有多少个结点

并且：只要是这个环中的结点，step都是环的长度（环上结点个数）

时间复杂度

参考文献

python3 代码

class UnionFind:
    def __init__(self, n):
        self.parent = [x for x in range(n)]
        self.size = [1 for x in range(n)]

    def Find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.Find(self.parent[x])
        return self.parent[x]

    def Union(self, x: int, y: int) -> bool:
        root_x = self.Find(x)
        root_y = self.Find(y)
        if root_x == root_y:
            return False
        if self.size[root_x] > self.size[root_y]:
            root_x, root_y = root_y, root_x
        self.parent[root_x] = root_y
        self.size[root_y] += self.size[root_x]
        return True

    def get_part_size(self, x: int) -> int:
        root = self.Find(x)
        return self.size[root]

T = int(input())
for _ in range(T):
    n = int(input())
    nums = [int(x) - 1 for x in input().split()]

    UF = UnionFind(n)
    for i, x in enumerate(nums):
        UF.Union(i, x)

    res = []
    for x in nums:
        res.append(UF.get_part_size(x))

    for x in res:
        print(x, end = ' ')
    print()

C++ 代码

#include<bits/stdc++.h>
using namespace std;

class UnionFind
{
public:
    vector<int> parent;
    vector<int> size;
    int part;

    UnionFind(int n)
    {
        parent.resize(n);
        for (int x = 0; x < n; x ++)
            parent[x] = x;
        size.resize(n, 1);
        part = n;
    }

    int Find(int x)
    {
        if (parent[x] != x)
            parent[x] = Find(parent[x]);
        return parent[x];
    }

    bool Union(int x, int y)
    {
        int root_x = Find(x);
        int root_y = Find(y);
        if (root_x == root_y)
            return false;
        if (size[root_x] > size[root_y])
            swap(root_x, root_y);
        parent[root_x] = root_y;
        size[root_y] += size[root_x];
        part --;
        return true;
    }

    int get_part_size(int x)
    {
        int root = Find(x);
        return size[root];
    }
};


int main()
{
    int T;    cin >> T;
    while(T --)
    {
        int n;    cin >> n;
        vector<int> nums(n);
        for (int i = 0; i < n; i ++)
        {
            cin >> nums[i];
            nums[i] --;         //为了从0开始，方便计算
        }

        UnionFind UF(n);
        for (int i = 0; i < n; i ++)
        {
            UF.Union(i, nums[i]);
        }

        vector<int> res;
        for (auto & x: nums)
            res.push_back(UF.get_part_size(x));     //连通分量（环）中，结点的个数。就像圆盘密码锁，同一圆盘，每个数转的距离一样
        for (auto x : res)
            cout << x << ' ';
        cout << endl;
    }

    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla