题解 | #MT18 重要节点#(广度优先搜索+图+哈希表)

解题思路

1.使用广度优先搜索分别计算当前节点的S值和T值,S值即为以当前节点i为起始点所有能访问的节点数,T值则为对所有节点执行广度优先搜索,当前节点i被访问的次数;

代码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    while(cin >> n >> m){
        int u, v;
        unordered_map<int, unordered_set<int>> f; //第二维使用set的原因在于输入中可能存在重边
        for(int i = 0; i < m; i++){
            cin >> u >> v;
            if(u == v) continue; //过滤掉自环
            f[u].insert(v); //u到v的有向边
        }
        vector<int> S(n + 1), T(n + 1); //当前节点能到的点集合大小及能到当前节点的点的集合大小
        for(int i = 1; i <= n; i++){
            //if(f.count(i) == 0) continue; //从当前节点出发能到的节点集合为0 S为0(不算自己本身)
            queue<int> q;
            vector<bool> isVisited(n + 1); //防止有环
            q.push(i);
            isVisited[i] = true;
            int cnt = 0; //统计节点i能到的点的个数 S值
            int curSize = 0;
            while(!q.empty()){
                curSize = q.size();
                cnt += curSize;
                for(int j = 0; j < curSize; j++){
                    int node = q.front();
                    T[node]++; //能到node节点的集合大小加1
                    q.pop();
                    if(f.count(node) == 0) continue;
                    for(auto& e : f[node]){
                        if(isVisited[e]) continue;
                        q.push(e);
                        isVisited[e] = true;
                    }
                }
            }
            S[i] = cnt;
        }
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(T[i] > S[i]) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}