NOIP 普及 2016 第一轮 第 18 题：社交关系图中的照片传播限制

题目

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】）。

解题过程

Lucia 发消息给朋友，朋友再转发给朋友的朋友（两步可达）。按原图：Lucia 的朋友集 ∪ 其朋友的朋友 = 两步邻域。按官方答案 Dana, Michael, Eve 收到消息（Peter/Jacob/Monica 不在两步邻域）。

选 A。

易错提醒

① 两步消息扩散 = 距离 ≤2 的点集（BFS 两层）；② 逐点核对与 Lucia 的最短距离。