题目来源：
https://www.nowcoder.com/practice/3b6060942397444cb0fe5846e230f6d9?tpId=90&tqId=30850&tPage=4&rp=4&ru=/ta/2018test&qru=/ta/2018test/question-ranking
题目描述：
给出一个图G(V,E)，图上有n个点，m条边，所有的边都是无向边。
最开始，也就是第0天的时候，这n个点中有一个点v感染了病毒，之后的每一天，凡是感染病毒的点都会向它的邻居点传播病毒。经过了t天之后，得到了感染病毒的点集S。要求找出第0天感染病毒的点v。如果v有很多不同的答案，把它们都找出来。
思路：
bfs算法，显然感染源一定是感染的点，先用ArrayLIst生成图，以每个感染的点为起点在t时间内进行广度遍历，将结果与给定的感染集合进行比较，如果一样则该点可以是感染源。
参考代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| public class Now_74 {
static boolean[] infected;
static ArrayList<Integer>[] graph;
static int n, m, k, t;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
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++){
int u = sc.nextInt();
int v = sc.nextInt();
graph[u].add(v);
graph[v].add(u);
}
k = sc.nextInt();
t = sc.nextInt();
for(int i = 0;i<k;i++){
infected[sc.nextInt()]=true;
}
List<Integer> res = new ArrayList<>();
for(int i=1;i<=n;i++){
if(infected[i] && bfs(i)){
res.add(i);
}
}
if(res.size()==0){
System.out.println(-1);
}
else {
for(int i=0;i<res.size();i++){
if(i==res.size()-1){
System.out.print(res.get(i));
}
else {
System.out.print(res.get(i)+" ");
}
}
}
}
private static boolean bfs(int x) {
int[] temp = new int[n+1];
LinkedList<Integer> queue = new LinkedList<>();
temp[x]=1;
queue.offer(x);
while (! queue.isEmpty()){
int cur = queue.poll();
if(temp[cur]>t) break;
for(Integer e : graph[cur]){
if(temp[e]==0){
temp[e]=temp[cur]+1;
queue.offer(e);
}
}
}
for(int i=1;i<=n;i++){
if(!infected[i] && temp[i]!=0) return false;
if(infected[i] && temp[i]==0) return false;
}
return true;
}
}
|
