B - Takahashi's Secret Editorial by en_translator


  • Friend \(X\), who learns Takahashi’s secret at first, tells the secret to Friend \(A_X\),
  • Friend \(A_X\) in turn tells the secret to Friend \(A_{A_X}\),
  • Friend \(A_{A_X}\) in turn tells the secret to Friend \(A_{A_{A_X}}\),
  • \(\cdots\)

and so on. That is, Takahashi’s secret becomes known as the event of “one friend tells the secret to another” happens repeatedly. This repetition goes on until the following event happens: “some Friend \(i\) tried to tell the secret to Friend \(A_i\), but Friend \(A_i\) already knew the secret.”

We solve the problem by simulating the process of the propagation of secret described above.
For example, one can simulate this propagation with the following algorithm, using a variable \(i\) and a boolean array \(b[\ast]\) that stores whether (\(true\)) or not (\(false\)) Friend \(i\) already knows his secret.

  1. Let \(i \leftarrow X\), and initialize all the elements of \(b[\ast]\) with \(false\).
  2. \(b[i] \leftarrow true\)
  3. \(i \leftarrow A_i\)
  4. \(b[i] = true\), then terminate. Otherwise go back to 2.

Then, count the number of friends who know the secret (i.e. the number of \(i\) among \(i = 1, 2, \ldots, N\) such that \(b[i] = true\) and output it, and it will be accepted for this problem.

A sample code in C++ language is shown below.

#include <iostream>
using namespace std;

int n, x;
int a[100001];
bool b[100001];

int main(void)
{
  cin >> n >> x;
  for(int i = 1; i <= n; i++) cin >> a[i];
  
  int i = x;
  do{
    b[i] = true;
    i = a[i];
  }while(!b[i]);
  
  int ans = 0;
  for(int i = 1; i <= n; i++) if(b[i]) ans++;
  cout << ans << endl;
  
  return 0;
}

posted:
last update: