トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) B - Takahashi's Secret
問題の要約
N人の友達がいる。それぞれ友達1,友達2,...,友達Nというあだ名で呼ばれている。
ある日,秘密を友達Xに知られてしまう。
i=1,2,...,Nについて,友達iが秘密を知ったとき,友達Aiがまだ秘密を知らなければ,友達iは秘密を友達Aiに教えてしまう。
秘密は最終的に何人の友達に知られることになるか?
制約
2<=N<=10^5
1<=X<=N
1<=Ai<=N
Ai≠i
入力
N X
A1 A2 ... AN
考え方
1,あだ名を1ずらす。
友達1,友達2,...,友達N => 友達0,友達1,...,友達N-1
よってXも1ずらす
0<=X<=N-1
2,秘密を知っているかどうかの情報をvector<int>で持つ。
3,Xから始めて,秘密を知っている友達に当たるまで,情報を更新しながらcountを増やしていく。
4,countを出力する。
実際のプログラム
#include<iostream>
#include<vector>
using namespace std;
int main(){
long long N,X;
cin >> N >> X;
X--;
vector<long long> A(N);
for(long long i = 0; i < N; i++){
cin >> A[i];
A[i]--;
}
vector<int> secret(N, 0);
long long count = 0;
while(secret[X] != 1){
secret[X] = 1;
X = A[X];
count++;
}
cout << count << endl;
return 0;
}