ABC311 C-Find it! (C++)
検討
ありうる経路について考えていたところ、制約から「すべての条件に行先が存在する」、すなわち、「行き止まりが無い」ことに気付きました。つまりどの頂点から出発してもいずれはループ(問題文でいう有向閉路)にたどり着くので、「(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使った。
この記事が気に入ったらサポートをしてみませんか?