原题传送门: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 分析与解析 #### 一、题目背景 在解决计算机科学中的算法问题时,经常会遇到组合数学的问题,特别是涉及到排列组合的计算。本题“浙大 oj1202Divide and Count”是一道典型的组合...
"基础C/C++ OJ(Online Judge)练习"是一个旨在帮助初学者提升C/C++编程技能的资源集合,通过解决一系列的编程题目来检验和增强理解力和实践能力。在这个压缩包中,我们找到了一个名为"(练习用)挑7.txt"的文件,很...
【OJ平台hustoj】是一个在线编程竞赛(Online Judge)平台的开源实现,它允许用户提交代码并自动运行测试,以验证程序的正确性。这个平台对于教学、技术比赛和编程训练非常有用,帮助学生和程序员提升编程技能。本文...
为了获知基因序列在功能和结构上的相似性,经常需要将几条不同序列的DNA进行比对,以判断该比对的DNA是否具有相关性。 现比对两条长度相同的DNA序列。首先定义两条DNA序列相同位置的碱基为一个碱基对,如果一个碱基...
【华为OJ C C++ OJ测试平台】标签表明了这个合集主要关注C和C++这两种编程语言。C语言是底层编程的基础,注重效率和内存管理,适合学习计算机系统原理和理解数据结构与算法;而C++作为C语言的扩展,增加了类、模板、...
南信大OJ部分题目答案
标题 "C编程 OJ习题 python" 暗示了这个主题是关于使用Python语言解决在线判断(Online Judge,简称OJ)系统中的C编程题目。C编程是一种基础且强大的编程语言,通常用于系统级编程、嵌入式系统以及算法竞赛。而...
北京邮电 OJ第一页 有问题例表,有正确答案可以给我谢谢 84 92 98 101 102 103 106 108 110 130 174 176 179 180 256 258 269 272 279 英文题就没有做 只做了第一页部分的题
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
湖南大学ACM-OJ的部分题目代码,对学习数据结构和算法很有帮助
这些文件名看起来是编程题目,很可能来源于在线编程竞赛(Online Judge,简称OJ)平台,如LeetCode、Codeforces或HackerRank等。每个.py文件可能代表一个独立的编程问题解决方案,采用Python语言编写。接下来,我们...
离线本地oj(Online Judge)练习系统是一种专为编程初学者设计的自我学习工具,它允许用户在没有网络连接的情况下进行编程练习。这样的系统通常包含了大量编程题目,涵盖各种算法和数据结构,帮助用户提高编程技能和...
现在有N列火车自东向西依次开过来了,按照到达的先后次序编号为0号到N-1号。 根据调度局的要求,小城A的调度站要改变这些列车驶离A城的顺序。 为了达到这一目的, 调度站在任意时刻可以执行以下三种操作之一:?...
计算浮点数的n次方,在北京大学的OJ网站上的题目,已经提交AC。可以作为参考。 原题如下: Description Problems involving the computation of exact values of very large magnitude and precision are common. ...
OJ系统的蓝桥杯题库,http://oj.xpuca.top/,这里有这些题的栗子。
HUSTOJ-SAE 安装次数 : 110 本系统为Online Judge 系统,可广泛用于教学、竞赛、招聘等用途。 九度OJ为本系统改造的典型案例。 文档、社区服务见项目首页,http://code.google.com/p/hustoj/ 安装应用 下载应用...
sduoj-sandbox.zip
很好的离线题库。。。。。 非常不错北大OJ题目
《OJ习题.zip》是一个包含了多个编程题目和相关知识点的压缩包,主要涉及C/C++编程语言的基础和进阶概念。以下是对每个文件名称所对应的知识点的详细解释: 1. **结构体、共用体和枚举** 结构体是C/C++中一种复合...