给出一个图 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天感染病毒的点如图
这道题你会答吗?花几分钟告诉大家答案吧!