102281: [AtCoder]ABC228 B - Takahashi's Secret
Description
Score : $200$ points
Problem Statement
Takahashi has $N$ friends. They have nicknames: Friend $1$, Friend $2$, $\ldots$, Friend $N$.
One day, Takahashi accidentally let one of his friends, Friend $X$, learn his shameful secret.
For each $i = 1, 2, \ldots, N$, when Friend $i$ learns the secret, he/she will share it with Friend $A_i$, if Friend $A_i$ has not already learned it.
How many of Takahashi's friends will learn the secret in the end?
Constraints
- $2 \leq N \leq 10^5$
- $1 \leq X \leq N$
- $1 \leq A_i \leq N$
- $A_i \neq i$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $X$ $A_1$ $A_2$ $\cdots$ $A_N$
Output
Print the answer.
Sample Input 1
4 2 3 1 1 2
Sample Output 1
3
Takahashi's secret will be learned by Friend $1$, Friend $2$, and Friend $3$, as follows.
- One day, Takahashi let Friend $2$ learn the secret.
- Friend $2$ shares it with Friend $1$.
- Friend $1$ shares it with Friend $3$.
In the end, three of his friends learn the secret, so we print $3$.
Sample Input 2
20 12 7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10
Sample Output 2
7
Input
题意翻译
高桥有 $n$ 个朋友,第 $i$ 个朋友的编号为 $i$ 。有一个长为 $n$ 的数列 $a_1,a_2,...,a_n$ ,表示如果朋友 $i$ 知道了一个秘密之后,会立马告诉朋友 $a_i$ 。 某日,朋友 $x$ 知道了高桥的一个秘密,并将这个秘密在高桥的这 $n$ 个朋友中按如上规则传来传去。请问:最后在高桥的朋友中会有多少人知道这个秘密呢?Output
得分:$200$分
问题描述
高桥有$N$个朋友。他们的昵称分别是:朋友$1$,朋友$2$,$\ldots$,朋友$N$。
有一天,高桥不小心让他的一个朋友,朋友$X$,得知了他的丑事。
对于每个$i = 1, 2, \ldots, N$,当朋友$i$得知这个秘密时,他/她会将它分享给朋友$A_i$,如果朋友$A_i$还没有得知这个秘密的话。
最后有多少个高桥的朋友会得知这个秘密呢?
限制条件
- $2 \leq N \leq 10^5$
- $1 \leq X \leq N$
- $1 \leq A_i \leq N$
- $A_i \neq i$
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出:
$N$ $X$ $A_1$ $A_2$ $\cdots$ $A_N$
输出
打印答案。
样例输入1
4 2 3 1 1 2
样例输出1
3
高桥的秘密会被朋友$1$,朋友$2$和朋友$3$得知,如下所示。
- 有一天,高桥让朋友$2$得知了这个秘密。
- 朋友$2$将它分享给了朋友$1$。
- 朋友$1$将它分享给了朋友$3$。
最后,有三个他的朋友得知了这个秘密,所以我们打印$3$。
样例输入2
20 12 7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10
样例输出2
7