Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 228 B 問題 Takahashi's Secret

AtCoder ABC ABC228 B問題 200 pts

問題

提出解答

問題の概要

$N$ 人の友達 (友達 $1, \dots$ , 友達 $N$ ) がいる. 友達 $i$ が高橋君の秘密を知り, 友達 $A_i$ は高橋君の秘密を知らないとき, 友達 $i$ は友達 $A_i$ に高橋君の秘密を教える.

最初, 友達 $X$ が高橋君の秘密を知り, 十分長い時間が経った場合, 高橋君の秘密を知っている友達は何人か?

制約

$2 \leq N \leq 10^5$
$1 \leq X \leq N$
$1 \leq A_i \leq N$
$A_i \neq i$
入力は全て整数である.

解法

高橋君の秘密の広がり方は一本道であり, 途中で枝分かれしない. このことから, 以下のような愚直な方法で求めることができる.

$T_1,T_2, \dots, T_N \gets \mathbb{F}$ とする.
$i \gets X$ とする.
である限り, 以下を実行する.
1. $T_i \gets \mathbb{T}$ とする (秘密を知る).
2. $i \gets A_i$ とする (秘密を伝える).
$T_i=\mathbb{T}$ となる $i$ の個数が答え.

計算量は, どんなに長くても $N$ 人で終わるので, $O(N)$ である.