题解 | 小红走迷宫

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cstring>
//经典的bfs
using namespace std;

const int N = 1e6 + 10;
const int M = 2e5 + 10;
int h[N],e[N],ne[N],idx;
bool st[M];

void add(int a,int b){
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int main() {

    int n,m,x;
    cin>>n>>m>>x;
    unordered_map<int, bool> trap;
    while(x--){
        int y;
        cin>>y;
        trap[y] = true;
    }
    memset(h, -1, sizeof h);
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    queue<int> q;
    vector<int> res;
    q.push(1);
    st[1] = true;
    res.push_back(1);
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        for(int i = h[t];i != -1;i = ne[i]){
            int tem = e[i];
            if(!st[tem] && !trap[tem]){
                q.push(tem);
                st[tem] = true;
                res.push_back(tem);
            }
        }
    }
    sort(res.begin(),res.end());
    for(auto t : res){
        cout<<t<<" ";
    }
}
// 64 位输出请用 printf("%lld")