L3-008 喊山 (30分)

这道题一开始想到用dfs来解决，但是看到这三个限制条件

  1. 输出的是山头的编号而不是几个山头
  2. 若这样的山头不只一个，则输出编号最小的那个。
  3. 若此山头的呼喊无法传到任何其他山头，则输出0。
    就准备去写bfs，PS：BFS好用来状态转移，来算最短路径

用邻接表来存放以山为点的图，队列存放该点和起点到该点的距离
编号最开始为该点，距离为0
如果距离相等，就找一个小一点的编号
如果距离不相等，小于该距离就更新，否则不更新
如果距离为0，就输出0（表示无法传到任何其他山头）

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>

using namespace std;

#define mm(a,x) memset(a,x,sizeof a)
#define PII pair<int,int>

const int N = 1e4 + 10;

vector<int> mp[N];
bool st[N];

int n,m,k,x;

int bfs(){
    queue<PII> q;
    st[x] = true;
    int minid = x,mindis = 0;
    q.push({x,0});
    while(q.size()){
        auto t = q.front();
        q.pop();
        int a = t.first;
        int b = t.second;
        if(mindis == b){
            minid = min(minid,a);
        }
        if(mindis < b){
            mindis = b;
            minid = a;
        }
        for(int i = 0; i < mp[a].size(); i ++ ){
            int c = mp[a][i];
            if(!st[c]){
                st[c] = true;
                q.push({c,b + 1});
            }
        }
    }
    if(mindis == 0){
        return 0;
    }
    return minid;
}

int main() {
    scanf("%d %d %d",&n,&m,&k);
    for(int i = 0; i < m; i ++ ){
        int a,b; cin >> a >> b;
        mp[a].push_back(b);
        mp[b].push_back(a);
    }
    for(int i = 0; i < k; i ++ ){
        cin >> x;
        mm(st,0);
        int ans = bfs();
        cout<<ans<<endl;
    }
    return 0;
}