制約欄に注目しましょう。

• 駅 \(1\) から駅 \(N\) に、同じ駅を2度訪れることなく到達可能であることが保証される

競技プログラミングにおいて、問題文や制約欄に「～であることが保証される」という言い回しがされることがしばしばあります。これは、前に書かれた条件を満たす入力しか与えられないということを問題が保証していることを意味します。

今回の例では、駅 \(1\) から駅 \(N\) に同じ駅を2度訪れることなく到達可能であることが保証されています。なので、 以下のようなことを行う必要はありません。

• 駅 \(1\) から駅 \(N\) に同じ駅を2度訪れることなく到達可能であるかを判定すること
• 駅 \(1\) から駅 \(N\) に同じ駅を2度訪れることなく到達不能であることをケアすること

本題に戻りましょう。

この問題では、駅 \(i\) からは駅 \(P_i\) に向かう電車しか走っていないため、駅 \(1\) から始めて、現在いる駅が \(x\) であれば駅 \(x\) から駅 \(P_x\) に向かうことを繰り返すことしかできないため、これを適切にシミュレートすればよいです。これは、 while 文などを適切に活用することで実現可能です。

先述した通り、この繰り返しによって駅 \(N\) に到達できることはこの問題が保証しており、また、駅 \(N\) に到達不能なケースをケアする必要はありません。

同じ駅を複数回通らずに駅 \(1\) から駅 \(N\) まで移動できることが保証されていることから、シミュレーション自体も最大 \(N\) ステップで完了することが分かります。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> p(n+1);
  for(int i=1;i<n;i++){
    cin >> p[i];
  }
  int res=1,pos=1;
  while(pos!=n){
    res++;
    pos=p[pos];
  }
  cout << res << "\n";
  return 0;
}