长沙教育建设信息网站,大型外包软件公司有哪些,外贸crm客户管理软件,顺德网站制作案例咨询喊山#xff0c;是人双手围在嘴边成喇叭状#xff0c;对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递#xff0c;回荡于深谷之间#xff0c;传送到人们耳中#xff0c;发出约定俗成的“讯号”#xff0c;达到声讯传递交流的目的。原来它是彝族先…喊山是人双手围在嘴边成喇叭状对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递回荡于深谷之间传送到人们耳中发出约定俗成的“讯号”达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”慢慢地人们在生活实践中发现了它的实用价值便把它作为一种交流工具世代传袭使用。
一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头本题请你找出这个信号最远能传达到的地方。
输入格式 输入第一行给出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思路 这道题是常规题用图的bfs遍历即可AC本题不需要其他的技巧进行优化。
不过这类题我在实际编写的时候发现使用dfs计算层数的时候总会出现一些问题过不了全部的测试点原因还在自查中…可能是需要一些方法吧所所以我们在做这类有关“计算层数”的题目时建议首先选择bfs。
参考代码
#includebits/stdc.h
using namespace std;
int n, m, k;
vectorint e[10005];
int vis[10005];
struct node{int v;int level;
};
int maxd, maxi;void bfs(int v)
{queuenode q;node t, temp;t.v v;t.level 1;vis[v] true;q.push(t);while(!q.empty()){t q.front();if(t.level maxd){maxd t.level;maxi t.v;}else if(t.level maxd t.v maxi)maxi t.v;q.pop();for(int i 0; i e[t.v].size(); i)if(vis[e[t.v][i]] false){temp.v e[t.v][i];temp.level t.level 1;q.push(temp);vis[temp.v] true;}}
}int main()
{scanf(%d %d %d, n, m, k);int a, b;for(int i 0; i m; i){scanf(%d %d, a, b);e[a].push_back(b);e[b].push_back(a);}int temp;for(int i 0; i k; i){scanf(%d, temp);memset(vis, false, sizeof(vis));if(e[temp].size() 0){printf(0\n);continue;}maxd -1;bfs(temp);printf(%d\n, maxi);}return 0;
}
