公式解説で、以下のアルゴリズムが実行時間制限を超過することを説明しました。

• \(i=1,2,\ldots,N\) の順に、以下の手順を行う。
  1. \(\operatorname{ans}\leftarrow i\) と初期化する。
  2. \(\operatorname{ans}\neq A _ {\operatorname{ans}}\) である限り、\(\operatorname{ans}\leftarrow A _ {\operatorname{ans}}\) と更新する。
  3. \(\operatorname{ans}\) を出力する。

ここで、2. の繰り返しを少し工夫することで最悪時間計算量を \(O(N\log N)\) に削減することができ、十分高速に動作します。

• \(i=1,2,\ldots,N\) の順に、以下の手順を行う。
  1. \(\operatorname{ans}\leftarrow i\) と初期化する。
  2. \(\operatorname{ans}\neq A _ {\operatorname{ans}}\) である限り、\(\mathbf{A _ {ans}\leftarrow A _ {A _ {ans}}}\) と更新し、\(\operatorname{ans}\leftarrow A _ {\operatorname{ans}}\) と更新する。
  3. \(\operatorname{ans}\) を出力する。

これは、union-find （素集合データ構造）で使われる path-halving と呼ばれる経路圧縮のテクニックです。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>

int main() {
    using namespace std;
    int N;
    cin >> N;

    vector<int> A(N);
    for (auto&& a : A) {
        cin >> a;
        --a; // 0-indexed にしておく
    }

    // 答えを順番に求める
    for (int ans : views::iota(0, N)) {
        while (ans != A[ans])
            ans = A[ans] = A[A[ans]]; // 経路圧縮をしながら探索
        cout << ans + 1 << " "; // 1-indexed に直して出力
    }
    cout << endl;

    return 0;
}