原题传送门:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1004
1004: Xi and Bo
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 275 Solved: 95
[Submit][Status][Web Board]
Description
Bo has been in Changsha for four years. However he spends most of his time staying his small dormitory. One day he decides to get out of the dormitory and see the beautiful city. So he asks to Xi to know whether he can get to another bus station from a bus station. Xi is not a good man because he doesn’t tell Bo directly. He tells to Bo about some buses’ routes. Now Bo turns to you and he hopes you to tell him whether he can get to another bus station from a bus station directly according to the Xi’s information.
Input
The first line of the input contains a single integer T (0<T<30) which is the number of test cases. For each test case, the first contains two different numbers representing the starting station and the ending station that Bo asks. The second line is the number n (0<n<=50) of buses’ routes which Xi tells. For each of the following n lines, the first number m (2<=m<= 100) which stands for the number of bus station in the bus’ route. The remaining m numbers represents the m bus station. All of the bus stations are represented by a number, which is between 0 and 100.So you can think that there are only 100 bus stations in Changsha.
Output
For each test case, output the “Yes” if Bo can get to the ending station from the starting station by taking some of buses which Xi tells. Otherwise output “No”. One line per each case. Quotes should not be included.
Sample Input
3
0 3
3
3 1 2 3
3 4 5 6
3 1 5 6
0 4
2
3 0 2 3
2 2 4
3 2
1
4 2 1 0 3
Sample Output
No
Yes
Yes
HINT
Source
分析:用并查集。对于每条公交路线,因为都是双向的,每个测试组的第一条公交路线的root 肯定是第一个站,对于剩下的公交路线,看看路线中是否包含这条以上路线的公交站,如果有就把那条路线合并到当前这条来,(f_a= fater[那条路线],father[f_a] = father[当前路线]);这样就把所有路线的集合合并了,最后判断father[起点] == father[终点] ?如果是则说明可以行得通,不是就over;
#include<cstdio> #define MAXM 110 int father[MAXM]; void init() { for(int i=0;i<MAXM;i++) father[i] = i; } int find(int a) { return father[a]==a?a:father[a] = find(father[a]); } void add(int a,int b) { int f_a = find(a); int f_b = find(b); if(f_a!=f_b) father[f_b] = f_a; } int t,s,e,n,m,head,x,y; int main() { scanf("%d",&t); while(t--) { init(); scanf("%d%d%d",&s,&e,&n); while(n--) { scanf("%d%d",&m,&x); head = find(x); for(int i=2;i<=m;i++) { scanf("%d",&y); y = find(y); add(head,y); } } printf("%s\n",find(s)==find(e)?"Yes":"No"); } }
相关推荐
浙大 oj1202Divide and Count代码c语言代码
搭建OJ平台的工具,方便大家搭建自己的OJ,建议大家使用ubuntu14.04版本,比较稳定
基础的c / c++ 练习题, 还有部分错误
OJ习题.zip
在线OJ网址大全在线OJ网址大全在线OJ网址大全在线OJ网址大全
很好的离线题库。。。。。 非常不错北大OJ题目
为了获知基因序列在功能和结构上的相似性,经常需要将几条不同序列的DNA进行比对,以判断该比对的DNA是否具有相关性。 现比对两条长度相同的DNA序列。首先定义两条DNA序列相同位置的碱基为一个碱基对,如果一个碱基...
八中oj代码
华为OJ测试平台的代码集合,可以借鉴代码例子,共同提高。
C语言实现的一道OJ题目,当中运用的算法是贪心算法。
oj题.zip
北京邮电 OJ第一页 有问题例表,有正确答案可以给我谢谢 84 92 98 101 102 103 106 108 110 130 174 176 179 180 256 258 269 272 279 英文题就没有做 只做了第一页部分的题
Ralphfjy 的oj题目
浙大oj试题1115 1216 1240 1241 1251 1312 1813 2240
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助
杭电OJ部分威士忌的代码 杭电OJ部分威士忌的代码杭电OJ部分威士忌的代码
PKU的oj分类 可以通过分类进行练习~~~
平顶山学院OJ试题离线版
现在有N列火车自东向西依次开过来了,按照到达的先后次序编号为0号到N-1号。 根据调度局的要求,小城A的调度站要改变这些列车驶离A城的顺序。 为了达到这一目的, 调度站在任意时刻可以执行以下三种操作之一:?...
杭电oj 1047习题