ABC311 C-Find it! (C++)

C - Find it!

検討

ありうる経路について考えていたところ、制約から「すべての条件に行先が存在する」、すなわち、「行き止まりが無い」ことに気付きました。つまりどの頂点から出発してもいずれはループ（問題文でいう有向閉路）にたどり着くので、「(1)適当な頂点から出発して、(2)経路を記録していって、(3)ループに突入した時点で処理を打ち切って、(4)ループ部を出力する」といった構成にしようと考えました。

回答

#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];

    int now_p = 1;
    set<int> searched;
    queue<int> route;

    while(true) {
        searched.insert(now_p);
        route.push(now_p);

        now_p = A[now_p];
        if (searched.count(now_p)) break;
    }
    
    while(true) {
        if (route.front() == now_p) break;
        route.pop();
    }

    cout << route.size() << endl;
    while(route.size() > 0) {
        cout << route.front() << " ";
        route.pop();
    }
}

実行時間137msでACでした。

なんとなく相性よさそうだったのでqueueで書いてみましたが、そのせいで探索済みの頂点をsetで別に管理することになっています。あんまり綺麗じゃない気がする。あと初めてqueue使った。