给出一个图 G(V,E) ,图上有 n 个点,m 条边,所有的边都是无向边。
最开始,也就是第 0 天的时候,这 n 个点中有一个点 v 感染了病毒,之后的每一天,凡是感染病毒的点都会向它的邻居点传播病毒。经过了 t 天之后,得到了感染病毒的点集 S 。要求找出第 0 天感染病毒的点 v 。如果 v 有很多不同的答案,把它们都找出来。
数据范围: , ,
给出一个图 G(V,E) ,图上有 n 个点,m 条边,所有的边都是无向边。
第一行两个数n,m,接下来有m行,每行两个数u,v,表示点u,v之间有一条无向边。接下来一行两个数k,t,其中k表示集合S的大小。最后一行k个数,集合S中的元素。输入的图可能有自环和重边,输入保证S中的数互不相同。
输出一行,如果不存在这样的v,输出-1。
否则输出所有可能的v,按照从小到大的顺序输出,数字之间用空格隔开,不要在行末输出多余的空格。
4 3 3 2 1 2 1 4 3 2 4 2 1
4
第0天,第1天,第2天感染病毒的点如图
病毒传播
暴力寻找每个被感染的点是否是起点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)); } } }