Title Description
Arrange 1 ∼ n in order to form a sequence.

The number I is just in position i.

Then give a position sequence p1,p2,..., pn with length N, which is an arrangement of 1 ∼ n.

Next, we will repeatedly perform the following operations on the sequence:

Rearrange the position of each number in the sequence and move the number at position i to position pi. (if i=pi, the number still moves to position i).
At the beginning of each operation, all numbers are moved at the same time. After the operation, the number sequence will become a new arrangement of 1 ∼ n.
For example, when n=6 and p=[4,6,1,3,5,2], after the first operation, the number 1 will move to position 4, the number 2 will move to position 6, and so on; After the second operation, the number 1 will move to position 3, the number 2 will move to position 2, and so on.

Your task is to determine how many times each number i from 1 to n returns to position i for the first time.

For example, considering p=[5,1,2,4,3], the moving track of number 1 is as follows:

After the first operation, position 5 is reached.
After the second operation, position 3 is reached.
After the third operation, position 2 is reached.
After the fourth operation, return to position 1.
Therefore, after four operations, the number 1 returns to position 1 for the first time.

It is worth mentioning that the number 4 returns to position 4 after one operation

Input format
The first row contains the integer T, which indicates a total of T groups of test data.

The first row of each set of data contains the integer n.

The second line contains n integers p1,..., pn.

Output format
Each group of data outputs a row of results, including n integers, in which the i-th integer represents the number of operations that the number I returns to position I for the first time.

Integers are separated by a single space.

Data range
For 30% of data, 1 ≤ T ≤ 10, 1 ≤ n ≤ 10.
For 100% data, 1 ≤ T ≤ 1000, 1 ≤ n ≤ 2 × 105，1≤pi≤n.
Ensure that p1 ∼ pn is an arrangement of 1 ∼ n.
Guarantee Σ n ≤ 2 × 105 (the sum of T N in one input shall not exceed 2 × 105).

Sample
 Input sample:
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
 Output example:
1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4 

(violence enumeration)
Go back to your position, a bit like and check the collection
Take these numbers as nodes in the graph. Each node returns to its own step, which is how many nodes are in the ring
And: as long as it is the node in the ring, step is the length of the ring (the number of nodes on the ring)

Time complexity
reference
C + + code

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

using namespace std;

const int N = 200010;

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

int find(int x) 
{
    return p[x]==x?p[x]:p[x]=find(p[x]);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) p[i] = i, s[i] = 1;
        for (int i = 1; i <= n; i ++ )
        {
            int j;
            scanf("%d", &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;
}

2. DFS (burst search)

Consider the arrangement as a graph in which point ii is connected to point pipi.

Then an arrangement on a graph must be many rings.

The number of times each number returns to itself for the first time is the length of its ring.

For each point, search its ring, find the ring length, and throw the answer to all points in the ring.

Time complexity
reference
C + + code

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n,t,p[N],res[N];
bool st[N];
int ans[N],x;
int dfs(int u)
{
    if(st[u])return 0;
    st[u]=true;
    ans[x++]=u;
    return dfs(p[u])+1;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(st, 0, sizeof st);
        for(int i=1;i<=n;i++)cin>>p[i];
        for(int i=1;i<=n;i++)
        {
            if(!st[i])
            {
                int t=dfs(i);
                for(int k=0;k<x;k++)res[ans[k]]=t;
                x=0;
            }
        }
        for (int i = 1; i <= n; i ++ )cout<<res[i]<<" ";
        puts("");
    }
    return 0;
}

Welcome to comment and like