思路:
开始太冲动直接写了个dfs发现不对,当一个地方发声则与该地点有边的点必定能听到了,直接dfs的话最远长度可能会变大,所以要用dfs一层一层标记完,当某个点的可达点都被标记完不能再向下标记时,该点就是此时最远的点,最远的点可能有好几个要比较保留最长的,长度相同则保存序号小的。
代码:
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define debug(a) cout << "debug : " << (#a) << " = " << a << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 998244353;
int n, m, k;
vector<int> a[N];
bool vis[N];
PII res;
void bfs(int x)
{
queue<PII> q;
q.push({x, 0});
vis[x] = true;
while (q.size())
{
PII t = q.front();
q.pop();
bool flag = true;
for (auto p : a[t.first])
{
if (!vis[p])
{
flag = false;
vis[p] = true;
q.push({p, t.second + 1});
}
}
if (flag)
{
if (res.second < t.second || res.second == t.second && res.first > t.first)
res = t;
}
}
}
int main()
{
cin >> n >> m >> k;
while (m--)
{
int l, r;
cin >> l >> r;
a[l].push_back(r), a[r].push_back(l);
}
while (k--)
{
memset(vis, false, sizeof vis);
int x;
cin >> x;
res = {x, 0};
bfs(x);
if (res.second == 0)
cout << 0 << endl;
else
cout << res.first << endl;
}
return 0;
}