首页 > 试题广场 >

病毒传播

[编程题]病毒传播

热度指数：2970 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个图 G(V,E) ，图上有 n 个点，m 条边，所有的边都是无向边。

最开始，也就是第 0 天的时候，这 n 个点中有一个点 v 感染了病毒，之后的每一天，凡是感染病毒的点都会向它的邻居点传播病毒。经过了 t 天之后，得到了感染病毒的点集 S 。要求找出第 0 天感染病毒的点 v 。如果 v 有很多不同的答案，把它们都找出来。

数据范围： $1 \le n,m \le 1000 \$ ， $1 \le k \le n \$ ， $1 \le t \le 10^9 \$

输入描述:

第一行两个数n，m，接下来有m行，每行两个数u，v，表示点u，v之间有一条无向边。接下来一行两个数k，t，其中k表示集合S的大小。最后一行k个数，集合S中的元素。输入的图可能有自环和重边，输入保证S中的数互不相同。

输出描述:

输出一行，如果不存在这样的v，输出-1。
否则输出所有可能的v，按照从小到大的顺序输出，数字之间用空格隔开，不要在行末输出多余的空格。

示例1

输入

输出

说明

第0天，第1天，第2天感染病毒的点如图

算法知识视频讲解

Python 3

Oliver1234

思路很直接，模拟每个点t天后的感染状况，如果与题目描述的S相同，则符合要求。

from collections import defaultdict
n, m = map(int, input().split()) # n个点，m条边
d = defaultdict(set) # 用d存储图，用set去重
for _ in range(m):
    p1, p2 = map(int, input().split())
    d[p1].add(p2)
    d[p2].add(p1)
k, t = map(int, input().split()) # s大小为k，共t天
s = set(map(int, input().split())) # s为最终感染情况
res = []

def check(v): # BFS搜索，检查v点在t天后感染情况是否与符合要求
    q = [v]
    infected = set([v]) # infected记录已经感染的地区
    for i in range(t):
        if not q: break
        for j in range(len(q)): # 每天找出新增的感染地区
            tmp = q.pop(0)
            for node in d[tmp]:
                if node not in infected:
                    q.append(node)
                    infected.add(node)
    if infected == s: # 如果感染情况与s一致，说明v符合要求，加入res
        res.append(v)

for v in s: # 遍历s中每个点，检查是否符合要求
    check(v)
if not res: print(-1)
else: print(' '.join(list(map(str,res))))

发表于 2022-02-06 18:19:02 回复(0)