给出一个图 G(V,E) ，图上有 n 个点，m 条边，所有的边都是无向边。
最开始，也就是第 0 天的时候，这 n 个点中有一个点 v 感染了病毒，之后的每一天，凡是感染病毒的点都会向它的邻居点传播病毒。经过了 t 天之后，得到了感染病毒的点集 S 。要求找出第 0 天感染病毒的点 v 。如果 v 有很多不同的答案，把它们都找出来。
数据范围： 
， 
，
[编程题]病毒传播
- 热度指数：2790 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行两个数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天感染病毒的点如图
显然感染源一定不是未感染的点，先求出任意两点间的最短距离，然后双重遍历所有点，如果两点都感染了且它们之间的最短距离>t，那么这两点予以排除，因为如果其中任一点是感染源，它们的最短距离又>t，那不可能在t时间内感染另一点；此外，如果一点感染了而另一点未感染且它们之间的距离<=t，那么也予以排除，因为如果感染的那一点是感染源，它应当能在t时间内通过最短距离感染到另一点。剩下的未被排除的就是可能的感染源。
一开始觉得n<=1000，弗洛伊德算法（复杂度O(n^3)）应该够，然而还是超时了，换了个思路，既然所有边等权，那用bfs能以O(m*n)求得所有最短距离，终于AC
import java.util.LinkedList;
import java.util.HashSet;
public class Main/*VirusTransmission2*/ {
final static int INF = 0x3f3f3f3f;
public static void main(String[] args) {
java.util.Scanner sc = new java.util.Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), i, t, inNum, flg;
int[][] G = new int[n][n];
boolean[] infected = new boolean[n], ans = new boolean[n];
HashSet<Integer>[] adj = new HashSet[n];
LinkedList<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[n];
for (i = 0; i < n; ++i) {
adj[i] = new HashSet<>();
java.util.Arrays.fill(G[i], INF);
G[i][i] = 0;
}
for (i = 0; i < m; ++i) {
int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
if (u != v) {
adj[u].add(v);
adj[v].add(u);
}
}
inNum = sc.nextInt();
t = sc.nextInt();
for (i = 0; i < inNum; ++i) {
int j = sc.nextInt() - 1;
infected[j] = ans[j] = true;
}
for (i = 0; i < n; ++i) {
java.util.Arrays.fill(visited, false);
visited[i] = true;
q.clear();
q.add(i);
while (!q.isEmpty()) {
int cur = q.pop();
for (Integer a : adj[cur]) {
if (!visited[a]) {
G[i][a] = G[i][cur] + 1;
q.add(a);
visited[a] = true;
}
}
}
}
for (i = 0; i < n; ++i) {
if (infected[i]) {
for (int j = 0; j < n; ++j) {
if (infected[j] && G[i][j] > t)
ans[i] = ans[j] = false;
else if (!infected[j] && G[i][j] <= t)
ans[i] = false;
}
}
}
for (flg = i = 0; i < n; ++i) {
if (ans[i]) {
System.out.printf("%s%d", flg == 0 ? "" : " ", i+1);
flg = 1;
}
}
System.out.println(flg == 0 ? "-1" : "");
}
}
编辑于 2018-08-03 20:03:58
回复(0)
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <unistd.h>
using namespace std;
bool breadth_first_search_algorithm(vector<vector<int>>& g,
const int n,
const int start,
const int t,
vector<int>& s) {
vector<int> seen(n + 1);
deque<int> q{{start}};
seen[start] = 1; // mark as seen
int days = 0;
vector<int> v; // 经过了t天之后，得到了感染病毒的点集 v
while (not q.empty() && days <= t) {
size_t s = q.size();
while (s--) {
const int cur = q.front(); q.pop_front();
v.emplace_back(cur);
for (const int nei : g[cur]) {
if (seen[nei]) continue;
q.emplace_back(nei);
seen[nei] = 1;
}
}
++days;
}
sort(begin(v), end(v));
return v == s;
};
void printAnswer(vector<int>& ans) {
for (auto iter = begin(ans); iter != end(ans); ++iter) {
cout << *iter;
if (iter < end(ans) - 1) cout << ' ';
}
cout << endl;
}
int main(void) {
// test 时间挑站
usleep(1E6 - 1000 * 100);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
while (m--) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
int k, t, x;
cin >> k >> t;
vector<int> s; // s 集合
while (k--) {
cin >> x;
s.emplace_back(x);
}
std::sort(begin(s), end(s));
vector<int> ans;
for (int u = 1; u <= n; ++u)
if (breadth_first_search_algorithm(g, n, u, t, s))
ans.emplace_back(u);
if (ans.empty()) cout << -1 << endl;
else printAnswer(ans);
return 0;
}
发表于 2021-07-13 13:49:40
回复(0)
#include <bits/stdc++.h>
using namespace std;
bool S[1001];
vector<int> G[1001];
int n, t;
bool BFS(int x) {
int vis[1001];
memset(vis, 0, sizeof(vis));
queue<int> q;
vis[x] = 1;
q.push(x);
int u;
while (!q.empty()) {
u = q.front();
q.pop();
if (vis[u] > t) break;
for (auto &v: G[u]) {
if (vis[v] == 0) {
vis[v] = vis[u] + 1;
q.push(v);
}
}
}
for (int i = 1; i <= n; i++) {
if (!S[i] && vis[i] != 0) return false;
if (S[i] && vis[i] == 0) return false;
}
return true;
}
int main() {
int m, u, v, cnt = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
int s, k;
scanf("%d%d", &k, &t);
for (int i = 1; i <= k; i++) {
scanf("%d", &s);
S[s] = true;
}
for (int i = 1; i <= n; i++) {
if(BFS(i)){
cnt++;
if(cnt==1)
printf("%d", i);
else
printf(" %d", i);
}
}
if (cnt == 0)
printf("-1");
printf("\n");
return 0;
}
发表于 2020-09-23 15:00:30
回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* @author wylu
*/
public class Main {
//感染病毒的点为true, 未感染的为false
static boolean[] infected;
static ArrayList<Integer>[] graph;
static int n, m, k, t;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strs = br.readLine().split(" ");
n = Integer.parseInt(strs[0]);
m = Integer.parseInt(strs[1]);
infected = new boolean[n + 1];
graph = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
//建图
for (int i = 0; i < m; i++) {
strs = br.readLine().split(" ");
int u = Integer.parseInt(strs[0]), v = Integer.parseInt(strs[1]);
graph[u].add(v);
graph[v].add(u);
}
strs = br.readLine().split(" ");
k = Integer.parseInt(strs[0]);
t = Integer.parseInt(strs[1]);
for (String s : br.readLine().split(" ")) {
infected[Integer.parseInt(s)] = true;
}
int res = 0;
for (int i = 1; i <= n; i++) {
if (infected[i] && bfs(i)) {
System.out.print((res++ > 0 ? " " : "") + i);
}
}
System.out.println((res == 0) ? "-1" : "");
}
//以x为起点传播t天的结果和实际结果比较是否相同
private static boolean bfs(int x) {
//每个点被传染需要的时间, 为0表明没有被传染
int[] cost = new int[n + 1];
LinkedList<Integer> queue = new LinkedList<>();
cost[x] = 1;
queue.offer(x);
while (!queue.isEmpty()) {
int cur = queue.poll();
if (cost[cur] > t) break;
for (Integer e : graph[cur]) {
if (cost[e] == 0) {
cost[e] = cost[cur] + 1;
queue.offer(e);
}
}
}
for (int i = 1; i <= n; i++) {
if (!infected[i] && cost[i] != 0) return false;
if (infected[i] && cost[i] == 0) return false;
}
return true;
}
}
发表于 2019-03-12 23:26:34
回复(0)
思路很直接，模拟每个点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)
bfs 模拟
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
/**
* @author zxy
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
// 构建图，点的范围在 [1:n]
HashSet[] edges = new HashSet[n + 1];
for (int i = 0; i < edges.length; i++) {
edges[i] = new HashSet();
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt(), b = sc.nextInt();
// 去自环
if (a != b) {
edges[a].add(b);
edges[b].add(a);
}
}
// 填充 infection 集合
int k = sc.nextInt(), t = sc.nextInt();
HashSet infection = new HashSet();
for (int i = 0; i < k; i++) {
infection.add(sc.nextInt());
}
// bfs 找起点
ArrayList res = new ArrayList();
for (int i = 1; i <= n; i++) {
if (bfs(edges, t, infection, i)) {
res.add(i);
}
}
// 输出
if (res.size() == 0) {
System.out.println(-1);
} else {
for (int i = 0; i < res.size() - 1; i++) {
System.out.print(res.get(i));
System.out.print(' ');
}
System.out.print(res.get(res.size() - 1));
}
}
// 层序遍历
private static boolean bfs(HashSet[] edges, int t, HashSet infection, int start) {
HashSet visited = new HashSet();
LinkedList queue = new LinkedList();
if (infection.contains(start)) {
queue.offer(start);
visited.add(start);
}
int days = 0;
while (!queue.isEmpty()) {
for (int i = queue.size(); i > 0; i--) {
Integer poll = queue.poll();
for (Integer next : edges[poll]) {
if (!infection.contains(next)) {
return false;
} else if (!visited.contains(next)) {
visited.add(next);
queue.offer(next);
}
}
}
if (++days == t) {
break;
}
}
return visited.size() == infection.size();
}
}
编辑于 2021-04-23 17:23:25
回复(0)
import collections
edges = set()
n, m = map(int, input().split())
# 去除边中的自环和重边，对于边(x, y)
# 若x == y则该边是自环，若(y, x)已在集合edges中，则(x, y)是重边
for _ in range(m):
x, y = map(int, input().split())
if x != y and not (y, x) in edges:
edges.add((x, y))
k, t = map(int, input().split())
nodes = list(map(int, input().split()))
# 建图
adj = collections.defaultdict(list)
for edge in edges:
x, y = edge
adj[x].append(y)
adj[y].append(x)
# BFS
res = []
for node in nodes:
queue = []
visited = [0]*(n+1)
queue.append(node)
visited[node] = 1
# h是感染的天数
h, infected = 0, []
infected.append(node)
while queue and h < t:
tmp = []
while queue:
nod = queue.pop()
for neighbor in adj[nod]:
if not visited[neighbor]:
tmp.append(neighbor)
visited[neighbor] = 1
h += 1
queue = tmp
infected += tmp
# t天结束后，若被感染的点集合infected和nodes中的点相同，则node是一个感染起点
if sorted(infected) == sorted(nodes):
res.append(node)
# 输出结果
n = len(res)
if n == 0:
print(-1)
res.sort()
for i in range(n - 1):
print(res[i], end=' ')
print(res[-1]) 各位大佬能帮忙看下我这段代码逻辑哪里出错了吗？一直是50%（python3)
编辑于 2020-08-13 12:33:57
回复(1)
病毒传播
暴力寻找每个被感染的点是否是起点v。对于每个起点v，广度优先遍历扩散一遍，扩散后结果和S集相同，则v是可能结果。
import java.util.*;
public class Main {
static boolean bfs(Set<Integer>[] g, int n, int x, boolean[] infected, int t, int k) {
LinkedList<Integer> q = new LinkedList<>();
Set<Integer> set = new HashSet<>();//存当前扩散到的点
q.offer(x); set.add(x);
int distance = 0;// 记录是第几天扩散到点
while(!q.isEmpty()) {
int size = q.size();
distance ++;
if(distance > t) break;// 超过t天，不需要继续了
for(int i=0; i < size; i++) {
int cur = q.poll();
for(int v : g[cur]) {
if(set.contains(v)) continue;//已经被访问，直接跳过
if(infected[v] == false) {
return false; //以x为起点，扩散到v,但实际v未被感染,因此，x一定非起点
}
q.offer(v); set.add(v);
}
}
}
//当t天后，扩散到的点刚好为k个时，符合题意。否则x一定不是起点
if(set.size() == k) return true;
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
Set<Integer>[] g = new HashSet[n+1]; // 去除重边
for(int i=1; i <= n; i++) g[i] = new HashSet<Integer>();
for(int i=0; i < m; i++) {
int u = sc.nextInt(), v = sc.nextInt();
if(u != v) { //去除自环
g[u].add(v); g[v].add(u);
}
}
int k =sc.nextInt(), t = sc.nextInt();
boolean[] infected = new boolean[n+1];
List<Integer> res = new ArrayList<>();
for(int i=0; i < k; i++) {
int v = sc.nextInt();
infected[v] = true;
}
for(int i=1; i <= n; i++) { // 暴力找起点
if(infected[i] && bfs(g, n, i, infected, t, k))
res.add(i);
}
if(res.size() == 0) {
System.out.println("-1");
} else {
for(int i=0; i < res.size()-1; i++)
System.out.print(res.get(i)+" ");
System.out.println(res.get(res.size()-1));
}
}
}
发表于 2020-07-01 22:43:50
回复(0)
import sys
from collections import deque
if __name__ == "__main__":
line = raw_input()
lines = line.split()
n = int(lines[0])
m = int(lines[1])
edges = []
for i in range(m):
line = raw_input()
lines = line.split()
edges.append([int(lines[0]), int(lines[1])])
line = raw_input()
lines = line.split()
k = int(lines[0])
t = int(lines[1])
S = []
line = raw_input()
lines = line.split()
for item in lines:
S.append(int(item))
V = set(range(1,n+1))
infected = set(S)
noninfect = V - infected
infected = list(infected)
noninfect = list(noninfect)
adjList = {}
for idx in range(1,n+1):
adjList[idx] = []
for i in range(len(edges)):
if edges[i][1] not in adjList[edges[i][0]] and edges[i][1] != edges[i][0]:
adjList[edges[i][0]].append(edges[i][1])
if edges[i][0] not in adjList[edges[i][1]] and edges[i][1] != edges[i][0]:
adjList[edges[i][1]].append(edges[i][0])
visited = [0 for i in range(n+1)]
graph = [[sys.maxint for i in range(n+1)] for j in range(n+1)]
for i in range(1,n+1):
graph[i][i] = 0
result = []
for item in infected:
depth = 1
visited = [0 for i in range(n+1)]
stack = []
stack1 = []
stack.append(item)
visited[item] = 1
while True:
tmp = stack.pop()
for node in adjList[tmp]:
if visited[node]==0 and node>=1 and node<=n:
stack1.append(node)
visited[node] = 1
if(graph[item][node]>depth):
graph[item][node] = depth
if len(stack) == 0:
stack = stack1
stack1 = []
depth += 1
if len(stack) == 0:
break
flag = 0
for jtem in noninfect:
if graph[item][jtem] <= t:
flag = 1
break
for ktem in infected:
if graph[item][ktem] >t:
flag = 1
break
if flag == 0:
result.append(item)
result.sort()
string = []
for item in result:
string.append(str(item))
if len(result) == 0:
print -1
else:
print " ".join(string)
发表于 2019-05-08 20:56:33
回复(0)
问题信息
难度：
9条回答
33收藏
3349浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
