题解 | #MT15 病毒传播#(广度优先搜索+哈希表)

解题思路

1.遍历每个节点,使用广度优先搜索验证当前点是否符合条件,简单模拟即可;

代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    while(cin >> n >> m){
        unordered_map<int, unordered_set<int>> f; //保存图(节点,相邻节点) 去掉重边
        int u, v;
        for(int i = 0; i < m; i++){
            cin >> u >> v;
            if(u == v) continue; //自环的时候就跳过
            f[u].insert(v);
            f[v].insert(u);
        }
        int k, t;
        cin >> k >> t;
        unordered_set<int> S; //感染病毒点集合S;
        int val;
        for(int i = 0; i < k; i++){
            cin >> val;
            S.insert(val);
        }
        vector<int> ans;
        for(int d = 1; d <= n; d++){　//遍历点集合,找出满足条件的点即可
            if(S.count(d) == 0) continue; //当前点没在感染病毒集合里,直接下一个
            queue<int> q;
            vector<bool> isVisited(n+1, false);
            q.push(d);
            isVisited[d] = true;
            int curSize, step = -1;
            bool flag = true; //标志当前点是否可以作为起始点
            while(!q.empty()){
                curSize = q.size();
                step++;
                if(step >= t) break; //注意这里要取等
                for(int i = 0; i < curSize; i++){
                    int node = q.front();
                    q.pop();
                    for(auto& e : f[node]){
                        if(S.count(e) == 0){ //邻居节点不在病毒感染集合里,当前点不可能为起始点
                            flag = false;
                            break;
                        }
                        if(isVisited[e]) continue;
                        q.push(e);
                        isVisited[e] = true;
                    }
                    if(!flag) break;
                }
                if(!flag) break;
            }
            if(!flag) continue;
            for(auto& d2 : S){ //isVisited中已访问的节点必定均在S中,判断S中的节点是否均被访问
                if(!isVisited[d2]){
                    flag = false;
                    break;
                }
            }
            if(!flag) continue; //当前点不满足条件,寻找下一个符合条件的起始点
            ans.push_back(d);
        }
        if(ans.size() == 0){
            cout << -1 << endl;
            continue;
        }
        for(int i = 0; i < ans.size(); i++){
            if(i < ans.size() - 1){
                cout << ans[i] << " ";
            }
            else{
                cout << ans[i] << endl;
            }
        }
    }
    return 0;
}