首页 > 试题广场 >

流言终结者

[编程题]流言终结者
  • 热度指数：209 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
在一个小镇住着n个人，其中有m对朋友关系。朋友关系是相互的，即A是B的朋友也意味着B是A的朋友。
这n个人分为两类：第一种人听到一个流言之后，会把它说给所有没有听过这个流言的朋友听。第二种人听到一个流言之后，不会把它说给任何一个朋友听。
现在有q次事件发生，每次事件形如"有一个人u听说了某个流言"，每次事件独立。
请问对于每一次事件，有多少人最终会听到这个流言？

输入描述:
第一行正整数n,m,q。
接下来m行，每行两个数字，表示初始的一对朋友关系，朋友关系不会重复给出
接下来一行n个数字,每个数字为1或者2，第i个数字表示第i个人属于第一种人/第二种人。
接下来一行q个整数，每个整数代表一次事件中最初听到的流言的人。



输出描述:
对于每个事件，输出一行一个整数，代表受影响的总人数
示例1

输入

5 5 5
1 2
2 3
3 4
4 5
1 5
1 2 1 1 2
1 2 3 4 5

输出

3
1
4
4
1

说明

第一次听到流言的人为{1,2,5}，第二、五次仅有初始时听到流言的人听到了，第三、四次是{2,3,4,5}
示例2

输入

6 7 5
1 2
1 4
1 6
4 6
3 5
1 5
2 6
1 2 1 1 1 2
1 2 3 5 6

输出

6
1
6
6
1
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-08-31 02:56:16
题目链接 流言终结者 题目描述 在一个小镇有 个人和 对朋友关系。朋友关系是相互的。 人分为两类： 传播者：听到流言后，会告诉所有没听过的朋友。 终结者：听到流言后，不会告诉任何人。 现在有 次独立的事件，每次事件都是某个人最先听到流言。请问每次事件最终有多少人会听到流言？ 解题思路 这是 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

图 广度优先搜索(BFS)
难度：
0条回答 88浏览

热门推荐

相关试题

流言终结者

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号