Planets Cycles

    1#include <bits/stdc++.h>
    2using namespace std;
    3 
    4void floyd_cycle(int x, const vector<int> &succ, vector<int> &ans){
    5    int a = succ[x], b = succ[succ[x]];
    6    // meet inside the cycle, but bail if we hit a known node
    7    while (a != b) {
    8        if (ans[a] || ans[b]) break;              // <<< early exit if chain already solved
    9        a = succ[a]; b = succ[succ[b]];
    10    }
    11    // Only do cycle work if we actually found a *new* cycle
    12    if (a == b && ans[a] == 0) {                  // <<< skip if cycle already labeled
    13        // find cycle entry
    14        a = x;
    15        while (a != b) { a = succ[a]; b = succ[b]; }
    16        int entry = a;
    17 
    18        // find cycle length
    19        int len = 1, nxt = succ[entry];
    20        while (nxt != entry) { nxt = succ[nxt]; len++; }
    21 
    22        // fill cycle nodes
    23        int v = entry;
    24        do { ans[v] = len; v = succ[v]; } while (v != entry);
    25    }
    26    // fill tail toward the first known node/cycle
    27    vector<int> path;
    28    int v = x;
    29    while (ans[v] == 0) { path.push_back(v); v = succ[v]; }
    30    for (int i = (int)path.size() - 1; i >= 0; --i)
    31        ans[path[i]] = ans[succ[path[i]]] + 1;
    32}
    33int main(){
    34    ios::sync_with_stdio(0);
    35    cin.tie(0);
    36    int n; cin >> n;
    37    vector<int> succ(n + 1), ans(n + 1);
    38    for(int i = 1; i <= n; i++){
    39        cin >> succ[i];
    40    }
    41    for(int i = 1; i <= n; i++){
    42        if(ans[i] == 0) floyd_cycle(i, succ, ans);
    43    }
    44    for(int i = 1; i <= n; i++){
    45        cout << ans[i] << (i == n ? "\n" : " ");
    46    }
    47    return 0;
    48}