NOIP 提高 2016 第一轮 第 12 题：Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们

题目

Lucia 和她的朋友以及朋友的朋友都在某社交网站上注册了账号。下图是他们之间的关系图，两个人之间有边相连代表这两个人是朋友，没有边相连代表不是朋友。这个社交网站的规则是：如果某人 A 向他（她）的朋友 B 分享了某张照片，那么 B 就可以对该照片进行评论；如果 B 评论了该照片，那么他 （她）的所有朋友都可以看见这个评论以及被评论的照片，但是不能对该照片进行评论（除非 A 也向他（她）分享了该照片）。现在 Lucia 已经上传了一张照片，但是她不想让 Jacob 看见这张照片，那么她可以向以下朋友（   ）分享该照片。

选项

• A. Dana, Michael, Eve
• B. Dana, Eve, Monica
• C. Michael, Eve, Jacob
• D. Micheal, Peter, Monica

答案

A

题解

考点定位

本题考「两步邻域」,对应大纲 3.3.3 图遍历（难度【3】）。

解题过程

与普及组同题：两步消息扩散，距离 ≤2 的点收到消息。官方答案 A（Dana, Michael, Eve）。

选 A。

易错提醒

① BFS 两层；② 逐点核对最短距离 ≤2。