路径数组变为统计数组

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

int n;
int dist(int *a, int *d, int k){
    if(d[k]>=0)
        return d[k];
    if(a[k]==k){
        d[k] = 0;
        return d[k];
    }
    d[k] = dist(a, d, a[k])+1;
    return d[k];
}

int main(){
    cin>>n;
    int a[n], d[n], r[n];
    memset(a, 0, sizeof(a));
    fill(d, d+n, -1);
    memset(r, 0, sizeof(r));
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        dist(a, d, i);
    for(int i=0;i<n;i++)
        if(d[i]>=0)
            r[d[i]]++;
    for(int i=0;i<n;i++)
        cout<<r[i]<<" ";
    return 0;
}

1、从左到右遍历paths，先遍历到位置0。 
 paths[0] == 9，首先令paths[0] == -1(这是为了标记起跳的城市)，因为城市0指向城市9，所以跳到城市9. 
 跳到城市9之后，paths[9] == 1，说明下一个城市是1，因为城市9是由城市0跳过来的，所以先令paths[9] = 0，然后跳向城市1。 
 跳到城市1之后，paths[1] == 1，说明城市1是首都。现在开始往回跳，城市1是由城市9跳过来的，所以跳回城市9。 
 根据之前设置的paths[9] == 0，我们知道城市9是由城市0跳过来的，在回跳之前先设置paths[9] = -1，表示城市9到首都的距离为1，之后回跳到0。 
 根据之前的设置paths[0] == -1，我们知道城市0是起跳位置，所以不再回跳，令paths[0] == -2，表示到首都的距离为2。 
 以上在跳向首都的过程中，paths数组有一个路径反指的过程，这是为了保证找到首都之后，能够完全跳回来。在跳回来的过程中，设置好这一路所跳的城市即可。
2、对于其他位置，跳跃的过程同上，但是跳跃终止的条件可以不是跳到首都，当我们跳到下一个位置发现它的值是负数，说明这个位置已经计算出了到首都的距离，我们只要在这个基础上来设置距离即可。
3、首都我们单独处理即可，找到首都的位置然后将它的值设为0，表示距离为0。
 得到距离数组后，数组中的距离值都用负数表示。接下来我们根据距离数组来计算得到统计数组。该过程也是一个跳跃的过程。从左到右遍历数组，假设遍历到为i，paths[i] == -j，那么我们可以知道城市i距离首都的距离是j，先令paths[i] == 0，表示此位置不再代表距离，然后跳到位置j处，如果位置j处的值为负数-k，我们令paths[j] = 1，表示我们已经找到一个距离为j的城市(城市i)。然后根据k继续往下跳。如果位置j处的值为正数，说明该位置已经是距离为j的城市的数量统计，直接加1即可。
#include<bits/stdc++.h>
using namespace std;
int main() {
    int n,cap=0,count=0;
    cin>>n;
    vector<int>path(n);
    map<int, vector<int>> mp;
    for(int i=0;i<n;i++)
    {
        cin>>path[i];
        if(path[i]==i)
            cap=i;
        else
            mp[path[i]].push_back(i);
    }
    deque<int> result,first,second;
    first.push_back(cap);
    while (!first.empty()) 
    {
        int tmp=first.front();
        first.pop_front();
        for(int i=0;i<mp[tmp].size();i++)
        {
            second.push_back(mp[tmp][i]);
            count++;
        }
        if(!first.empty())
            continue;
        else
        {
            result.push_back(count);
            first = second;;
            second.clear();
            count = 0;
        }
    }
    result.push_front(1);
    while (result.size() > path.size()) 
        result.pop_back();
    while (result.size() < path.size()) 
        result.push_back(0);
    int length = path.size();
    path.clear();
    for (int i = 0; i < length; ++i)
        cout<<result[i]<<" ";
    return 0;
}