AtCoder ABC 228 B - Takahashi's Secret (5Q, 灰色, 200 点)

これ結構難しい気がする！　グラフの問題の一種。

• 問題へのリンク

問題概要

人 がいる。高橋君（ 人のいずれとも異なる）は、自分の秘密を、この中の人 に知られてしまった。

一般に、人 は新たに秘密を知ったときには、人 にも伝えてしまう。

高橋君の秘密は最終的に何人に知られるか？

考えたこと

人 は人 に秘密を伝え、さらにその秘密が人 に伝わり......を繰り返していくこととなる。

これが 人全員に伝わるかというと、そうとは限らない。ある段階で人 が人 に秘密を伝えたとき、もし人 がすでに秘密を知っていたら、秘密の伝播が終了するのだ。

この秘密の伝播をシミュレートするために、次の配列 known を用意しよう。

---

• known[v] ← 人 が秘密を知っている状態のとき true、そうでないとき false

---

この配列を使って、秘密が伝播していく様子を実装しよう。その時その時の「最も最近秘密を知った人」を表す変数 cur を用意する。最初、cur = X である。そして、次のようにシミュレートしていけばよい。

cur = X;
while (known[cur]) {
    known[cur] = true;
    cur = A[cur];
}

あとは、実装の細部を詰めれば AC となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, X;
    cin >> N >> X;
    --X;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i], --A[i];

    
    vector<bool> known(N, false);
    int res = 0, cur = X;
    while (!known[cur]) {
        known[cur] = true;
        res++;
        cur = A[cur];
    }
    cout << res << endl;
}