Java BFS 题解 | #病毒传播#

import java.util.*;

public class Main {
    // 声明变量
    static int n, sz, m, k, t;
    static Set<Integer>[] table;
    static boolean[] infected;

    private static void dealWithInput() {
        Scanner sc = new Scanner(System.in);
        sz = (n = sc.nextInt()) + 1; // 使用节点的逻辑索引
        m = sc.nextInt();
        // 初始化图
        infected = new boolean[sz];
        table = (Set<Integer>[]) new HashSet[sz]; // 边去重
        for (int xl = 1; xl < sz; xl++) table[xl] = new HashSet<Integer>();
        // 读取接下来数据
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt();
            if(u != v) {
                table[u].add(v);
                table[v].add(u);
            }
        }
        k = sc.nextInt();
        t = sc.nextInt();
        for(int i = 0; i < k; i++) {
            infected[sc.nextInt()] = true; // 也可以使用 set
        }
    }

    // 遍历感染集中每一个结点，BFS 访问。若半径范围内的结点出现未感染，则返回 false，
    private static List<Integer> solution() {
        List<Integer> ans = new ArrayList<>();
        for (int node = 1; node < sz; node++) {
            if (infected[node] && check(node))
                ans.add(node);
        }
        return ans;
    }

    private static boolean check(int node) { // 检查结点是否符合传染源的条件
        // 需要队列、vis[]
        Queue<Integer> queue = new LinkedList<>();
        boolean[] vis = new boolean[sz];

        queue.offer(node);
        vis[node] = true;
        int setCnt = 0, sz;
        // 需要出队 1 + t 次。最后一次的入队不做处理
        for (int nout = 0; nout < t + 1 && (sz = queue.size()) > 0; nout++) {
            while (sz-- > 0) {
                int poll = queue.poll();
                // 进行判断
                if (!infected[poll]) return false;
                ++setCnt; // 表示被传染结点的个数

                // 加入相邻结点
                for (int next : table[poll]) {
                    if (!vis[next]) {
                        queue.offer(next);
                        vis[next] = true; // 入队时标记为已访问
                    }
                }
            }
        }
        
        return setCnt == k;
    }

    public static void main(String[] args) {
        dealWithInput();
        List<Integer> ans = solution();
        if (ans.size() > 0) {
            System.out.print(ans.get(0));
            for (int i = 1; i < ans.size(); i++) {
                System.out.printf(" " + ans.get(i));
            }
        } else {
            System.out.println(-1);
        }
    }
}