[32]病毒传播-美团点评2018秋

1.题目描述

给出一个图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≤10^3, 0≤m≤10^3 ,1≤t≤10^9,1≤u,v,k≤n,S中所有元素在区间[1,n] ）
• 输出描述：
  输出一行，如果不存在这样的v，输出-1。
  否则输出所有可能的v，按照从小到大的顺序输出，数字之间用空格隔开，不要在行末输出多余的空格。
• 输入样例：

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

• 输出样例：

  4
  

• 说明：
  第0天，第1天，第2天感染病毒的点如图。

  
  

2.题目解析

• 重要知识
  自环(Loop) : 一条边的起点与终点为同一顶点。
  重边(Multi-Edges) : 多条边的起点与终点完全相同。
  图的存储方式：邻接表
  图的遍历方式：深度遍历(DFS)/广度遍历(BFS)

依次把感染的每个点作为第0感染病毒的点，然后计算经过了t天之后的感染结果。拿这个结果与点集S比较。
感染方式属于广度遍历(BFS).

3.参考答案

#include <bits/stdc++.h>
using namespace std;

int main(){
   int n = 0; // 顶点数
   int m = 0; // 边数
   scanf("%d%d",&n,&m);
   vector<int> vec[n+1]; // 邻接表，下标表示顶点
   for(int i=0;i<m;++i){
       int u = 0;
       int v = 0;
       scanf("%d%d",&u,&v);
       vec[u].push_back(v);
       vec[v].push_back(u);
   }
   int k = 0;
   int t = 0;
   scanf("%d%d",&k,&t);
   set<int> S;
   for(int i=0;i<k;++i){
       int s;
       scanf("%d",&s);
       S.insert(s);
   }
   bool has = false;
   for(int v:S){
      set<int> infect;
      queue<int> q;              // 定义队列
      int visited[n+1];           // 定义标记顶点是否已访问
      fill_n(visited,n+1,-1);   // 初始化为未访问
      infect.insert(v);
      visited[v] = 0;         // 标记v已经访问
      q.push(v);                 // 入队v
      while (!q.empty()) {       // 队列非空
        int now = q.front();     // 取出队首元素
        q.pop();                 // 队首元素出队
        for (int i = 0; i < vec[now].size(); i++) { // 遍历v的邻接点
          int post = vec[now][i];// 取出邻接点
          if (visited[post] == -1 && visited[now] <t) {  // 判断邻接点是否访问
            visited[post] = visited[now]+1;// 标记邻接点已访问
            infect.insert(post);
            q.push(post);        // 邻接点入队
          }
        }
      }
      if(S == infect){
         printf("%d ",v);
         has = true;
      }
   }
    if(!has)
       printf("-1\n");
   return 0;
}

牛客题目