実は、以下の手順で答えを見つけることができます。

• 最初に、通った頂点を記録する列 \(S\) を用意する。 \(S\) は最初は空である。
• その後、好きな頂点 \(v\) から始めて以下を繰り返す。
  • \(S\) に \(v\) が含まれない場合
    • \(S\) の末尾に \(v\) を追加し、 \(v \rightarrow A_v\) の辺を伝って \(v\) から \(A_v\) に移動する。
  • \(S\) に \(v\) が含まれる場合
    • \(S = (x_1, x_2, \dots, v, y_1, y_2,\dots, y_k)\) であったとする。
    • このとき、 \((v, y_1, y_2, \dots, y_k)\) が答えの一例となる。
    • なぜなら、 \(v \rightarrow y_1, y_i \rightarrow y_{i+1}\) ( \(1 \le i \le k-1\) ) に加えて \(y_k \rightarrow v\) の辺が存在し、これは閉路だからである。

問題の制約より、全ての頂点についてそこから出る辺が存在するので、この手順で必ず閉路が発見できます。

\(S\) に \(v\) が含まれるかどうかの判定をバケットソートの要領で行うことで、時間計算量 \(O(N)\) でこの問題に正解できます。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n+1);
  for(int i=1;i<=n;i++){
    cin >> a[i];
  }

  vector<int> fl(n+1,0),s;
  int v=1; // any vertex is ok to start
  while(fl[v]==0){
    fl[v]=1;
    s.push_back(v);
    v=a[v];
  }

  vector<int> res;
  for(auto &nx : s){
    if(nx==v){v=-1;}
    if(v==-1){res.push_back(nx);}
  }
  cout << res.size() << "\n";
  for(int i=0;i<res.size();i++){
    if(i){cout << " ";}
    cout << res[i];
  }cout << "\n";
  return 0;
}