L3-008 喊山
喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。（图文摘自：http://news.xrxxw.com/newsshow-8018.html）
一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。
输入格式：
输入第一行给出3个正整数 \(n\)、\(m\) 和 \(k\)，其中 \(n\)（ \(≤10000\) ）是总的山头数（于是假设每个山头从 \(1\) 到 \(n\) 编号）。接下来的 \(m\) 行，每行给出2个不超过 \(n\) 的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出 \(k\)（ \(≤10\) ）个不超过 \(n\) 的正整数，数字间用空格分开，代表需要查询的山头的编号。
输出格式：
依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出 \(0\) 。
输入样例：
7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7
输出样例：
2
6
4
0
解题思路
这道题一开始我理解错了题意，题干中给出的比较关键的条件在于 一个山头呼喊的声音可以被临近的山头同时听到。而我一开始没太在意这个，直接通过样例来理解题目意思了，而正是因为如此，导致我理解错题意，一直只能拿到 21 分。（不过我觉得陈越老师有时应当解释解释样例哈，不然真的老是理解错题目呜呜呜呜）
我先讲讲我一开始错误的理解，对于这个样例，通过画图之后可以看出有三个连通块，其中第一个连通块是存在环的，而第一个查询的节点是1，从1传到最远的地方答案给出的是2，而题目中说的是传到距离最远的点，所以，我就理解成了，因为连通块中包含环，所以1到达其它任意点的距离都是无限远，此时取编号最小的点输出即可；而如果查询的点的所属连通块内不含环，那么就可以通过 \(dfs\) 求得从当前点出发到任意一点的距离，然后枚举得到最远的且编号尽量小的点即可。
所以，延续着这个错误的理解，我先用一个 \(dfs\) 求出所有连通块，并将每个连通块有哪些点都存储起来，在每求完一个连通块后，利用拓扑排序判断无向图是否存在环，来标记每个连通块是否有环。这些都是预处理的操作。最后，没输入一个需要查询的点，第一，要找到这个点所在连通块；第二，要判断所在连通块是否存在环，或者是不是独立的点，此时就要输出最小的点（情况1 存在环）或者输出0（情况2 独立的点），否则，就需要再用另一个 \(dfs\) 求得当前点到其它各点的距离；第三，枚举所有点，查找到最远且编号最小的点进行答案的输出。
下面是我错误的杰作，21分呜呜呜呜呜呜
/* 一切都是命运石之门的选择 El Psy Kongroo */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
//typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 10010, M = 4 * N;
int h[N], e[M], ne[M], idx;
int n, m, k;
int dist[N];
int ind[N]; //度数
bool vis[N];
map<int, bool> hasCir; //判断是否存在环
vector<int> block[N]; //每个连通块的点
int cnt;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
ind[b] ++ ;
}
//dfs求连通块
void dfs(int u){
vis[u] = true;
block[cnt].push_back(u);
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i];
if(vis[v]) continue;
dfs(v);
}
}
//dfs求源点到各点距离
void dfs2(int u, int fa){
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i];
if(v == fa) continue;
dist[v] = dist[u] + 1; //自顶向下
dfs2(v, u);
}
}
//拓扑排序判断无向图是否存在环
bool topo(int id){
int cnt = 0;
queue<int> q;
for(auto &v : block[id])
if(ind[v] <= 1) q.push(v); //度数小于等于1的入队
while(!q.empty()){
int u = q.front();
q.pop();
cnt ++ ;
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i];
ind[v] -- ;
if(ind[v] == 1) q.push(v);
}
}
return cnt != (int)block[id].size();
}
//若存在环 需要连通块内编号最小且不是源点的点
int find_min(int i, int u){
int res = inf;
for(auto &v : block[i])
if(v != u) res = min(v, res);
return res;
}
void solve(int u){
int id = 0;
for(int i = 1; i <= cnt; i ++ )
if(find(block[i].begin(), block[i].end(), u) != block[i].end()){
id = i; //找到查询点所属连通块
break;
}
if(hasCir[id]) {
int minv = find_min(id, u);
if(minv == inf) cout << 0 << endl;
else cout << minv << endl;
return;
}
memset(dist, 0, sizeof(dist));
dfs2(u, -1);
int res = 0, ansv = 0;
for(auto &v : block[id])
if(v != u && dist[v] > res) res = dist[v], ansv = v;
cout << ansv << endl;
return;
}
void show(int i){
for(auto &v : block[i]) cout << v << ' ';
cout << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
memset(h, -1, sizeof(h));
cin >> n >> m >> k;
while(m -- ){
int u, v; cin >> u >> v;
add(u, v), add(v, u);
}
for(int i = 1; i <= n; i ++ )
if(!vis[i]) cnt ++ , dfs(i), hasCir[cnt] = topo(cnt);
while(k -- ){
int u; cin >> u;
solve(u);
}
return 0;
}
由于这个错误思想，我写了两个 \(dfs\) 和一个 \(topo排序\) ，结果最后拿了 21 分，而且我本以为这么多东西运行时间会很长，而实际上似乎效率还可以（虽然是错的）。
所以，这告诉我们真的要认真读题，不然就像我这样......在错误的道路上越走越深。
关键的条件在于 一个山头呼喊的声音可以被临近的山头同时听到，根据这一点，我们其实可以知道，这个其实是广度优先搜索的操作，就是从一个点开始，然后扩散到周围所有邻接的点，然后再扩散......所以这其实就是 \(bfs\) 求点的层次，并记录层次最高且编号最小的点。根本没有什么环，没有什么拓扑排序，哇哇哇哇（；´д｀）ゞ
最后的解答还是比较简单的。
/* 一切都是命运石之门的选择 El Psy Kongroo */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
//typedef __int128 int128;
#define PI acos(-1.0)
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 10010, M = 4 * N;
int h[N], e[M], ne[M], idx;
int dist[N];
bool vis[N];
int n, m, k;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int bfs(int src){
int res = src, maxd = 0;
queue<int> q;
q.push(src);
vis[src] = true;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = h[u]; ~i; i = ne[i]){
int v = e[i];
if(vis[v]) continue;
dist[v] = dist[u] + 1;
q.push(v);
vis[v] = true;
if(dist[v] > maxd) maxd = dist[v], res = v;
else if(dist[v] == maxd && v < res) res = v; //编号更小
}
}
return res == src ? 0 : res; //如果是独立的点 输出0
}
int solve(int u){
memset(dist, 0, sizeof(dist));
memset(vis, 0, sizeof(vis));
return bfs(u);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
memset(h, -1, sizeof(h));
while(m -- ){
int u, v; cin >> u >> v;
add(u, v), add(v, u);
}
while(k -- ){
int u; cin >> u;
cout << solve(u) << endl;
}
return 0;
}