病毒传播

import java.util.LinkedList;
import java.util.HashSet;
 
public class Main/*VirusTransmission2*/ {
  final static int INF = 0x3f3f3f3f;
  public static void main(String[] args) {
    java.util.Scanner sc = new java.util.Scanner(System.in);
    int n = sc.nextInt(), m = sc.nextInt(), i, t, inNum, flg;
    int[][] G = new int[n][n];
    boolean[] infected = new boolean[n], ans = new boolean[n];
    HashSet<Integer>[] adj = new HashSet[n];
    LinkedList<Integer> q = new LinkedList<>();
    boolean[] visited = new boolean[n];
    for (i = 0; i < n; ++i) {
      adj[i] = new HashSet<>();
      java.util.Arrays.fill(G[i], INF);
      G[i][i] = 0;
    }
    for (i = 0; i < m; ++i) {
      int u = sc.nextInt() - 1, v = sc.nextInt() - 1;
      if (u != v) {
        adj[u].add(v);
        adj[v].add(u);
      }
    }
    inNum = sc.nextInt();
    t = sc.nextInt();
    for (i = 0; i < inNum; ++i) {
      int j = sc.nextInt() - 1;
      infected[j] = ans[j] = true;
    }
    for (i = 0; i < n; ++i) {
      java.util.Arrays.fill(visited, false);
      visited[i] = true;
      q.clear();
      q.add(i);
      while (!q.isEmpty()) {
        int cur = q.pop();
        for (Integer a : adj[cur]) {
          if (!visited[a]) {
            G[i][a] = G[i][cur] + 1;
            q.add(a);
            visited[a] = true;
          }
        }
      }
    }
    for (i = 0; i < n; ++i) {
      if (infected[i]) {
        for (int j = 0; j < n; ++j) {
          if (infected[j] && G[i][j] > t)
            ans[i] = ans[j] = false;
          else if (!infected[j] && G[i][j] <= t)
            ans[i] = false;
        }
      }
    }
    for (flg = i = 0; i < n; ++i) {
      if (ans[i]) {
        System.out.printf("%s%d", flg == 0 ? "" : " ", i+1);
        flg = 1;
      }
    }
    System.out.println(flg == 0 ? "-1" : "");
  }
}

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <unistd.h>

using namespace std;

bool breadth_first_search_algorithm(vector<vector<int>>& g,
                                    const int n,
                                    const int start,
                                    const int t,
                                    vector<int>& s) {  
  vector<int> seen(n + 1);
  deque<int> q{{start}};
  seen[start] = 1; // mark as seen
  
  int days = 0;
  vector<int> v; // 经过了t天之后，得到了感染病毒的点集 v
  while (not q.empty() && days <= t) {
    size_t s = q.size();
    while (s--) {
      const int cur = q.front(); q.pop_front();
      v.emplace_back(cur);
      for (const int nei : g[cur]) {
        if (seen[nei]) continue;
        q.emplace_back(nei);
        seen[nei] = 1;
      }
    }
    ++days;
  }
  
  sort(begin(v), end(v));
  return v == s;
};


void printAnswer(vector<int>& ans) {
  for (auto iter = begin(ans); iter != end(ans); ++iter) {
    cout << *iter;
    if (iter < end(ans) - 1) cout << ' ';
  }
  cout << endl;
}

int main(void) {
  
  // test 时间挑站
  usleep(1E6 - 1000 * 100);
  
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n + 1);
  while (m--) {
    int u, v;
    cin >> u >> v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  
  int k, t, x;
  cin >> k >> t;
  vector<int> s; // s 集合
  while (k--) {
    cin >> x;
    s.emplace_back(x);
  }
  
  std::sort(begin(s), end(s));
  vector<int> ans;
  for (int u = 1; u <= n; ++u)
    if (breadth_first_search_algorithm(g, n, u, t, s))
      ans.emplace_back(u);
  
  if (ans.empty()) cout << -1 << endl;
  else printAnswer(ans);
  
  return 0;
}

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

bool S[1001];
vector<int> G[1001];
int n, t;

bool BFS(int x) {
    int vis[1001];
    memset(vis, 0, sizeof(vis));
    queue<int> q;
    vis[x] = 1;
    q.push(x);
    int u;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        if (vis[u] > t) break;
        for (auto &v: G[u]) {
            if (vis[v] == 0) {
                vis[v] = vis[u] + 1;
                q.push(v);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!S[i] && vis[i] != 0) return false;
        if (S[i] && vis[i] == 0) return false;
    }
    return true;
}

int main() {
    int m, u, v, cnt = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int s, k;
    scanf("%d%d", &k, &t);
    for (int i = 1; i <= k; i++) {
        scanf("%d", &s);
        S[s] = true;
    }
    for (int i = 1; i <= n; i++) {
        if(BFS(i)){
            cnt++;
            if(cnt==1)
                printf("%d", i);
            else
                printf(" %d", i);
        }
    }
    if (cnt == 0)
        printf("-1");
    printf("\n");
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

/**
 * @author wylu
 */
public class Main {
    //感染病毒的点为true, 未感染的为false
    static boolean[] infected;
    static ArrayList<Integer>[] graph;
    static int n, m, k, t;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        n = Integer.parseInt(strs[0]);
        m = Integer.parseInt(strs[1]);
        infected = new boolean[n + 1];
        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        
        //建图
        for (int i = 0; i < m; i++) {
            strs = br.readLine().split(" ");
            int u = Integer.parseInt(strs[0]), v = Integer.parseInt(strs[1]);
            graph[u].add(v);
            graph[v].add(u);
        }

        strs = br.readLine().split(" ");
        k = Integer.parseInt(strs[0]);
        t = Integer.parseInt(strs[1]);
        for (String s : br.readLine().split(" ")) {
            infected[Integer.parseInt(s)] = true;
        }

        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (infected[i] && bfs(i)) {
                System.out.print((res++ > 0 ? " " : "") + i);
            }
        }
        System.out.println((res == 0) ? "-1" : "");
    }

    //以x为起点传播t天的结果和实际结果比较是否相同
    private static boolean bfs(int x) {
        //每个点被传染需要的时间, 为0表明没有被传染
        int[] cost = new int[n + 1];
        LinkedList<Integer> queue = new LinkedList<>();
        cost[x] = 1;
        queue.offer(x);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            if (cost[cur] > t) break;
            for (Integer e : graph[cur]) {
                if (cost[e] == 0) {
                    cost[e] = cost[cur] + 1;
                    queue.offer(e);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (!infected[i] && cost[i] != 0) return false;
            if (infected[i] && cost[i] == 0) return false;
        }
        return true;
    }
}

from collections import defaultdict
n, m = map(int, input().split()) # n个点，m条边
d = defaultdict(set) # 用d存储图，用set去重
for _ in range(m):
    p1, p2 = map(int, input().split())
    d[p1].add(p2)
    d[p2].add(p1)
k, t = map(int, input().split()) # s大小为k，共t天
s = set(map(int, input().split())) # s为最终感染情况
res = []

def check(v): # BFS搜索，检查v点在t天后感染情况是否与符合要求
    q = [v]
    infected = set([v]) # infected记录已经感染的地区
    for i in range(t):
        if not q: break
        for j in range(len(q)): # 每天找出新增的感染地区
            tmp = q.pop(0)
            for node in d[tmp]:
                if node not in infected:
                    q.append(node)
                    infected.add(node)
    if infected == s: # 如果感染情况与s一致，说明v符合要求，加入res
        res.append(v)

for v in s: # 遍历s中每个点，检查是否符合要求
    check(v)
if not res: print(-1)
else: print(' '.join(list(map(str,res))))

bfs 模拟

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
/**
 * @author zxy
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        // 构建图，点的范围在 [1:n]
        HashSet[] edges = new HashSet[n + 1];
        for (int i = 0; i < edges.length; i++) {
            edges[i] = new HashSet();
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt();
            // 去自环
            if (a != b) {
                edges[a].add(b);
                edges[b].add(a);
            }
        }
        // 填充 infection 集合
        int k = sc.nextInt(), t = sc.nextInt();
        HashSet infection = new HashSet();
        for (int i = 0; i < k; i++) {
            infection.add(sc.nextInt());
        }
        // bfs 找起点
        ArrayList res = new ArrayList();
        for (int i = 1; i <= n; i++) {
            if (bfs(edges, t, infection, i)) {
                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.print(' ');
            }
            System.out.print(res.get(res.size() - 1));
        }
    }
    // 层序遍历
    private static boolean bfs(HashSet[] edges, int t, HashSet infection, int start) {
        HashSet visited = new HashSet();
        LinkedList queue = new LinkedList();
        if (infection.contains(start)) {
            queue.offer(start);
            visited.add(start);
        }
        int days = 0;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                Integer poll = queue.poll();
                for (Integer next : edges[poll]) {
                    if (!infection.contains(next)) {
                        return false;
                    } else if (!visited.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
            if (++days == t) {
                break;
            }
        }
        return visited.size() == infection.size();
    }
}

import collections
edges = set()
n, m = map(int, input().split())
# 去除边中的自环和重边，对于边(x, y)
# 若x == y则该边是自环，若(y, x)已在集合edges中，则(x, y)是重边
for _ in range(m):
    x, y = map(int, input().split())
    if x != y and not (y, x) in edges:
        edges.add((x, y))

k, t = map(int, input().split())
nodes = list(map(int, input().split()))

# 建图
adj = collections.defaultdict(list)
for edge in edges:
    x, y = edge
    adj[x].append(y)
    adj[y].append(x)

# BFS
res = []
for node in nodes:
    queue = []
    visited = [0]*(n+1)
    queue.append(node)
    visited[node] = 1
    # h是感染的天数
    h, infected = 0, []
    infected.append(node)
    while queue and h < t:
        tmp = []
        while queue:
            nod = queue.pop()
            for neighbor in adj[nod]:
                if not visited[neighbor]:
                    tmp.append(neighbor)
                    visited[neighbor] = 1
        h += 1
        queue = tmp
        infected += tmp
    # t天结束后，若被感染的点集合infected和nodes中的点相同，则node是一个感染起点
    if sorted(infected) == sorted(nodes):
        res.append(node)

# 输出结果       
n = len(res)
if n == 0:
    print(-1)

res.sort()
for i in range(n - 1):
    print(res[i], end=' ')
print(res[-1])

病毒传播

暴力寻找每个被感染的点是否是起点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));
        }
    }
}

import sys
from collections import deque
if __name__ == "__main__":
    
    line = raw_input()
    lines = line.split()
    n = int(lines[0])
    m = int(lines[1])
    
    edges = []
    for i in range(m):
        line = raw_input()
        lines = line.split()
        edges.append([int(lines[0]), int(lines[1])])
    
    line = raw_input()
    lines = line.split()
    k = int(lines[0])
    t = int(lines[1])
    
    S = []
    line = raw_input()
    lines = line.split()
    for item in lines:
        S.append(int(item))
    
    V = set(range(1,n+1))
    infected = set(S)
    noninfect = V - infected
    infected = list(infected)
    noninfect = list(noninfect)

    adjList = {}
    for idx in range(1,n+1):
        adjList[idx] = []
    
    for i in range(len(edges)):
        if edges[i][1] not in adjList[edges[i][0]] and edges[i][1] != edges[i][0]:
            adjList[edges[i][0]].append(edges[i][1])
        if edges[i][0] not in adjList[edges[i][1]] and edges[i][1] != edges[i][0]:
            adjList[edges[i][1]].append(edges[i][0])
            
    visited = [0 for i in range(n+1)]
    graph = [[sys.maxint for i in range(n+1)] for j in range(n+1)]
    for i in range(1,n+1):
        graph[i][i] = 0
    
    result = []
    for item in infected:
        depth = 1
        visited = [0 for i in range(n+1)]
        stack = []
        stack1 = []
        stack.append(item)
        visited[item] = 1
        while True:
            tmp = stack.pop()
            for node in adjList[tmp]:
                if visited[node]==0 and node>=1 and node<=n:
                    stack1.append(node)
                    visited[node] = 1
                
                if(graph[item][node]>depth):
                    graph[item][node] = depth
            
            if len(stack) == 0:
                stack = stack1
                stack1 = []
                depth += 1
            
            if len(stack) == 0:
                break
    
        flag = 0
        for jtem in noninfect:
            if graph[item][jtem] <= t:
                flag = 1
                break
        for ktem in infected:
            if graph[item][ktem] >t:
                flag = 1
                break
        if flag == 0:
            result.append(item)
    
    result.sort()
    string = []
    for item in result:
        string.append(str(item))
    
    if len(result) == 0:
        print -1
    else:
        print " ".join(string)