题解 | #病毒传播#

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAXN = 1005;
vector<int> graph[MAXN];  // 邻接表存储图
bool infected[MAXN];      // 最终感染状态
int infTime[MAXN];       // 感染时间
int n, m, k, t;

// BFS检查从起点v开始是否能得到给定结果
bool check(int v) {
    fill(infTime, infTime + n + 1, 0);
    queue<int> q;
    q.push(v);
    infTime[v] = 1;  // 初始时间为1

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        if (infTime[curr] > t) break;  // 超过时间t就停止

        // 遍历相邻节点
        for (int next : graph[curr]) {
            if (infTime[next] == 0) {  // 未访问过
                infTime[next] = infTime[curr] + 1;
                q.push(next);
            }
        }
    }

    // 验证结果
    for (int i = 1; i <= n; i++) {
        if ((infected[i] && infTime[i] == 0) || 
            (!infected[i] && infTime[i] != 0)) {
            return false;
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    
    // 建图
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    // 读取感染结果
    cin >> k >> t;
    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        infected[x] = true;
    }
    
    // 检查每个点作为起点
    vector<int> result;
    for (int i = 1; i <= n; i++) {
        if (check(i)) {
            result.push_back(i);
        }
    }
    
    // 输出结果
    if (result.empty()) {
        cout << "-1" << endl;
    } else {
        for (int i = 0; i < result.size(); i++) {
            if (i > 0) cout << " ";
            cout << result[i];
        }
        cout << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static final int MAXN = 1005;
    static ArrayList<Integer>[] graph = new ArrayList[MAXN];
    static boolean[] infected = new boolean[MAXN];
    static int[] infTime = new int[MAXN];
    static int n, m, k, t;
    
    // BFS检查从起点v开始是否能得到给定结果
    static boolean check(int v) {
        Arrays.fill(infTime, 0);
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        infTime[v] = 1;  // 初始时间为1
        
        while (!q.isEmpty()) {
            int curr = q.poll();
            if (infTime[curr] > t) break;  // 超过时间t就停止
            
            // 遍历相邻节点
            for (int next : graph[curr]) {
                if (infTime[next] == 0) {  // 未访问过
                    infTime[next] = infTime[curr] + 1;
                    q.offer(next);
                }
            }
        }
        
        // 验证结果
        for (int i = 1; i <= n; i++) {
            if ((infected[i] && infTime[i] == 0) || 
                (!infected[i] && infTime[i] != 0)) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        // 初始化图
        for (int i = 0; i < MAXN; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 建图
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }
        
        // 读取感染结果
        k = sc.nextInt();
        t = sc.nextInt();
        for (int i = 0; i < k; i++) {
            infected[sc.nextInt()] = true;
        }
        
        // 检查每个点作为起点
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (check(i)) {
                result.add(i);
            }
        }
        
        // 输出结果
        if (result.isEmpty()) {
            System.out.println("-1");
        } else {
            for (int i = 0; i < result.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(result.get(i));
            }
            System.out.println();
        }
    }
}

from collections import defaultdict, deque
from typing import List, Set

def check(v: int, graph: defaultdict, infected: Set[int], n: int, t: int) -> bool:
    """BFS检查从起点v开始是否能得到给定结果"""
    inf_time = [0] * (n + 1)
    q = deque([v])
    inf_time[v] = 1  # 初始时间为1
    
    while q:
        curr = q.popleft()
        if inf_time[curr] > t:  # 超过时间t就停止
            break
            
        # 遍历相邻节点
        for next_node in graph[curr]:
            if inf_time[next_node] == 0:  # 未访问过
                inf_time[next_node] = inf_time[curr] + 1
                q.append(next_node)
    
    # 验证结果
    for i in range(1, n + 1):
        if (i in infected and inf_time[i] == 0) or \
           (i not in infected and inf_time[i] != 0):
            return False
    return True

def main():
    # 读取图的基本信息
    n, m = map(int, input().split())
    
    # 建图
    graph = defaultdict(list)
    for _ in range(m):
        u, v = map(int, input().split())
        graph[u].append(v)
        graph[v].append(u)
    
    # 读取感染结果
    k, t = map(int, input().split())
    infected = set(map(int, input().split()))
    
    # 检查每个点作为起点
    result = []
    for i in range(1, n + 1):
        if check(i, graph, infected, n, t):
            result.append(i)
    
    # 输出结果
    if not result:
        print("-1")
    else:
        print(" ".join(map(str, result)))

if __name__ == "__main__":
    main()