题目描述:
喊山
喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。
一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头,本题请你找出这个信号最远能传达到的地方。
输入格式:
输入第一行给出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
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int h[N],ne[N], e[N], idx;//邻接表数据结构
int dist[N];//存储距离
int st[N];//标记点是否走到过
int n, m, k;
void add(int a, int b)//邻接表存储图
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs(int u)
{
memset(dist, 0x3f, sizeof(dist));//初始都没有走到过,距离无穷大
memset(st, 0, sizeof st);
dist[u] = 0;//从1号节点开始,距离为0
queue<int> q;//队列
q.push(u);//1号节点入队列
st[u] = 1;//1到1的距离为0,已经求出
while(q.size())//对列非空,就一直往后搜索
{
int t = q.front();//队头出队,找该点能到的点
q.pop();
for(int i = h[t]; i != -1; i = ne[i])//遍历所有t节点能到的点,i为节点索引
{
int j = e[i];//通过索引i得到t能到的节点编号
if(!st[j])//如果没有遍历过
{
dist[j] = dist[t] + 1;//距离为t号节点的距离+1
q.push(j);//节点入队
st[j] = 1;//入队后标记,已经遍历过了
}
}
}
int pox = 0x3f3f3f3f,d = 0;
for(int i = 1;i <= n;i ++)
if(dist[i] != 0x3f3f3f3f && dist[i] > d)
d = dist[i];
for(int i = 1;i <= n;i ++)
if(dist[i] == d && d != 0)
pox = min(i, pox);
if(pox == 0x3f3f3f3f) return 0;
return pox;
}
int main()
{
cin >> n >> m >> k;
memset(h, -1, sizeof h);//初始化,所有节点没有后继,后继都是-1
for(int i = 0; i < m; i++)//读入所有边
{
int a, b;
cin >> a >> b;
add(a, b);//加入邻接表
add(b, a);
}
for(int i = 0;i < k;i ++){
int x;
cin>>x;
cout<<bfs(x)<<endl;
}
return 0;
}
来源模板: 图中点的层次