给出一个图 G(V,E) ，图上有 n 个点，m 条边，所有的边都是无向边。
最开始，也就是第 0 天的时候，这 n 个点中有一个点 v 感染了病毒，之后的每一天，凡是感染病毒的点都会向它的邻居点传播病毒。经过了 t 天之后，得到了感染病毒的点集 S 。要求找出第 0 天感染病毒的点 v 。如果 v 有很多不同的答案，把它们都找出来。
数据范围： 
， 
，
[编程题]病毒传播
- 热度指数：2970 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行两个数n，m，接下来有m行，每行两个数u，v，表示点u，v之间有一条无向边。接下来一行两个数k，t，其中k表示集合S的大小。最后一行k个数，集合S中的元素。输入的图可能有自环和重边，输入保证S中的数互不相同。
输出描述:
输出一行，如果不存在这样的v，输出-1。
否则输出所有可能的v，按照从小到大的顺序输出，数字之间用空格隔开，不要在行末输出多余的空格。
示例1
输入
4 3 3 2 1 2 1 4 3 2 4 2 1
输出
4
说明
第0天，第1天，第2天感染病毒的点如图
import java.util.*;
public class Main {
// 声明变量
static int n, sz, m, k, t;
static Set<Integer>[] table;
static boolean[] infect
展开全文
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Sca
展开全文
解题思路
这是一道使用BFS解决的病毒传播问题，主要思路如下：
问题分析：
给定一个无向图
从某个起点 开始传播病毒
每天病毒会传播给相邻节点
给定 天后的感染结果
求所有可能的起始点
解决方案：
使用BFS模拟病毒传播过程
对每个点作为起点进行验证
记录每个点被感染的时间
比
展开全文
问题信息
难度：
9条回答
37收藏
4781浏览
通过挑战的用户
查看代码-
2023-03-05 18:52:03
-
2022-09-03 19:18:42 -
2022-09-02 20:15:59
-
2022-09-01 23:16:30
-
2022-08-31 18:49:08
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
