美团笔试-病毒传播

描述

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

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

输入描述：

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

输出描述：

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

示例1

输入：

4 3 3 2 1 2 1 4 3 2 4 2 1

输出：

4

说明：

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

 

解题思路：

这道题是一道典型的图题目，可以利用邻接表构建图，二维数组存储，然后利用一个数组标记那些被感染的点；题目要求从小到大输出可能的起始点，然后根据感染点以及广度优先搜索（bfs）判断在t时间内能否导致感染相同的点即可。

#include <bits/stdc++.h> using namespace std;/*以x为起点传播t天的结果与实际（题目给的结果）比较*/ bool bfs(vector<vector<int>>& adj,int x,int t,vector<int>& infected){/*每个点被感染需要的时间*/vector<int> cost(infected.size()+1,-1);queue<int> q;cost[x]=0;//起始时间为0q.push(x);while(!q.empty()){auto u=q.front();q.pop();if(cost[u]>=t) break;for(auto& v:adj[u]){if(cost[v]==-1){cost[v]=cost[u]+1;q.push(v);}}}for(int i=1;i<=infected.size();++i){if(!infected[i]&&cost[i]!=-1) return false;if(infected[i]&&cost[i]==-1) return false;}return true; }int main(int argc,char* argv[]){int n,m,k,t;cin>>n>>m;vector<vector<int>> adj(n+1);for(int i=0;i<m;++i){//建立邻接表int u,v;cin>>u>>v;adj[u].push_back(v);adj[v].push_back(u);}vector<int> infected(n+1,0);cin>>k>>t;for(int i=0;i<k;++i){//记录感染的int v;cin>>v;infected[v]=1;//从小到大}vector<int> res;for(int i=1;i<=n;++i){if(infected[i]&&bfs(adj,i,t,infected)){//只有感染的才需要检测res.push_back(i);}}for(auto& r:res)printf("%d ",r);if(res.empty())printf("%d",-1);cout<<endl;return 0; }

总结

以上是生活随笔为你收集整理的美团笔试-病毒传播的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。