病毒传播

C++ 解法, 执行用时: 18ms, 内存消耗: 448KB, 提交时间: 2020-11-14

#include <bits/stdc++.h>
using namespace std;
bool ans[1005]; //感染了病毒的点标记为  1 没感染为 0
int temp[1005]; // bfs 过程中每个点最早被传染的时间    为  0说明没被传染
vector<int> vec[1005];//用邻接表表示的边集
queue<int> q; // bfs 中用到的队列
int n, t;
bool ok(int x) {//用 bfs 跑出以  x 为起点    传播  t 天的结果比较和实际结果是否相同
    for (int i = 1; i <= n; i++) temp[i] = 0;
    while (!q.empty()) q.pop();
    //以上是预处理
    temp[x] = 1;
    q.push(x);
    int now;
    while (!q.empty()) {
        now = q.front();
        q.pop();
        if (temp[now] > t) break;
        for (int i = 0; i < vec[now].size(); i++) {
            if (temp[vec[now][i]] == 0) {
                temp[vec[now][i]] = temp[now] + 1;
                q.push(vec[now][i]);
            }
        }
    }
    //以上是 bfs 可以保证复杂度  o(n)
    for (int i = 1; i <= n; i++) {
        if (ans[i] == 0 && temp[i] != 0) return 0;
        if (ans[i] != 0 && temp[i] == 0) return 0;
    }
    //以上是验证是否符合给出的点集
    return 1;
}
int main() {
  int m, u, v, num = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  //以上是建图
  int s, k;
  scanf("%d%d", &k, &t);
  for (int i = 1; i <= k; i++) {
    scanf("%d", &s);
    ans[s] = 1;
  }
  //标记被感染的点
  for (int i = 1; i <= n; i++) {
    if (ok(i)){ //输出符合结果的点
      if (num > 0) printf(" "); //防止行末空格
      num++;
      printf("%d", i);
    }
  }
  if (num == 0) //无解
    printf("-1");
  printf("\n");
  return 0;
}

C++ 解法, 执行用时: 18ms, 内存消耗: 508KB, 提交时间: 2020-10-29

#include <bits/stdc++.h>
using namespace std;
bool ans[1005]; //感染了病毒的点标记为  1 没感染为 0
int temp[1005]; // bfs 过程中每个点最早被传染的时间    为  0说明没被传染
vector<int> vec[1005];//用邻接表表示的边集
queue<int> q; // bfs 中用到的队列
int n, t;
bool ok(int x) {//用 bfs 跑出以  x 为起点    传播  t 天的结果比较和实际结果是否相同
    for (int i = 1; i <= n; i++) temp[i] = 0;
    while (!q.empty()) q.pop();
    //以上是预处理
    temp[x] = 1;
    q.push(x);
    int now;
    while (!q.empty()) {
        now = q.front();
        q.pop();
        if (temp[now] > t) break;
        for (int i = 0; i < vec[now].size(); i++) {
            if (temp[vec[now][i]] == 0) {
                temp[vec[now][i]] = temp[now] + 1;
                q.push(vec[now][i]);
            }
        }
    }
    //以上是 bfs 可以保证复杂度  o(n)
    for (int i = 1; i <= n; i++) {
        if (ans[i] == 0 && temp[i] != 0) return 0;
        if (ans[i] != 0 && temp[i] == 0) return 0;
    }
    //以上是验证是否符合给出的点集
    return 1;
}
int main() {
  int m, u, v, num = 0;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &u, &v);
    vec[u].push_back(v);
    vec[v].push_back(u);
  }
  //以上是建图
  int s, k;
  scanf("%d%d", &k, &t);
  for (int i = 1; i <= k; i++) {
    scanf("%d", &s);
    ans[s] = 1;
  }
  //标记被感染的点
  for (int i = 1; i <= n; i++) {
    if (ok(i)){ //输出符合结果的点
      if (num > 0) printf(" "); //防止行末空格
      num++;
      printf("%d", i);
    }
  }
  if (num == 0) //无解
    printf("-1");
  printf("\n");
  return 0;
}

详情