B - Trained?: AtCoder Beginner Contest 065

問題文

筋力をつけたい高橋君は、AtCoder 社のトレーニング設備で、トレーニングをすることにしました。 AtCoder 社のトレーニング設備には N 個のボタンがついており、ちょうど 1 個のボタンが光っています。 ボタンには、1 から N までの番号がついています。 ボタン i が光っているときにそのボタンを押すと、ボタン i の明かりが消え、その後ボタン a_i が光ります。i=a_i であることもあります。 光っていないボタンを押しても、何も起こりません。 最初、ボタン 1 が光っています。高橋君は、ボタン 2 が光っている状態で、トレーニングをやめたいと思っています。 そのようなことは可能かどうか判定し、もし可能なら最低で何回ボタンを押す必要があるかを求めてください。

制約

2≦N≦105

1≦a_i≦N

結果:TLE

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
const int NMAX = 100000;
int main(){
    int N;
    vector<int> a;
    vector<int> passed;
    int button = 0;
    cin >> N;
    for (int i =0; i <N; ++i) {
        int input;
        cin >> input;
        a.push_back(input);
    }
    
    int on_now = 1;
    passed.push_back(on_now);
    for (int i =0; i <NMAX; ++i) { //pressing i-th button
        on_now = a[on_now-1];
        auto itr = std::find(passed.begin(), passed.end(), on_now);
        if( itr != passed.end() ) {
            cout << -1 << endl;
            break;
        }
        
        passed.push_back(on_now);
        button += 1;
        if (on_now == 2) {
            cout << button << endl;
            break;
        }
        
    }
    
    return 0;
}