ABC228B Takahashi's Secret
题目分析¶
高桥有 $N$ 个朋友，每个朋友 $i$ 会把秘密告诉另一个指定的朋友 $A_i$（只会告诉一个人）。
当某个朋友得知秘密后，他会立即传播给他的目标朋友，前提是对方还不知道。
一开始只有朋友 $X$ 知道秘密。我们要统计最终有多少个朋友会知道这个秘密。
从传播方式看，这是一个单向的传递链，每个人只会告诉一个人。
解题思路¶
可以把这个传播过程看作是从节点 $X$ 开始的一条路径，每次跳到 $A_i$ 指向的人，直到遇到已经访问过的节点为止。
为了避免重复传播，我们使用一个布尔数组 vis 标记哪些人已经知道秘密。
从 X 开始，一步一步跳到 A[x]，每跳一步，就标记该人已经知道秘密，直到跳到一个已经被标记的人为止。
实现步骤¶
- 读入 $N$ 和 $X$；
- 用数组
A[100005]存每个人要告诉的朋友编号； - 定义布尔数组
vis[100005]初始化为全false； - 使用变量
cur = X表示当前传播到的人； - 使用
while(true)循环模拟传播过程：- 如果
vis[cur] == true，跳出； - 否则标记
vis[cur] = true； - 然后更新
cur = A[cur]跳到下一个人；
- 如果
- 遍历
vis数组，统计为true的个数。
复杂度分析¶
- 时间复杂度：$O(N)$，每个朋友最多只被访问一次；
- 空间复杂度：$O(N)$，用于存储数组
A和访问标记数组vis。
总结¶
- 本题可以建模为从某个起点出发的一条链式传播路径；
- 用布尔数组记录访问状态，防止重复；
- 模拟传播过程，直到遇到环或终点；
- 实现简单，效率高，适合用
while循环处理。