【題解】CSES 1751 Planets Cycles

【題目敘述】https://cses.fi/problemset/task/1751/

#include <iostream>
using namespace std;
 
int n, a[200005][20], b[200005], ans[200005];
 
int f(int x){
    if (ans[x]) return ans[x];
    return ans[x] = f(a[x][0])+1;
}
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i][0];
    }
    for (int i = 1; i < 20; i++){
        for (int j = 1; j <= n; j++){
            a[j][i] = a[a[j][i-1]][i-1];
        }
    }
    for (int i = 1; i <= n; i++){
        b[a[i][19]] = 1;
        if (ans[a[i][19]]) continue;
        int now = a[a[i][19]][0];
        ans[a[i][19]]++;
        while (now != a[i][19]){
            now = a[now][0];
            ans[a[i][19]]++;
        }
        now = a[now][0];
        while (now != a[i][19]){
            ans[now] = ans[a[i][19]];
            now = a[now][0];
        }
    }
    for (int i = 1; i <= n; i++){
        if (!ans[i]) ans[i] = f(i);
    }
    for (int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
}
分享本文 Share with friends