小希的

news/2024/11/24 2:35:21/

小希的迷宫-杭电地址

					小希的迷宫

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 65877 Accepted Submission(s): 20676

problem Description
上次Gardon的迷宫城堡小希玩了很久(见Problem B),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子,前两个是符合条件的,但是最后一个却有两种方法从5到达8。

在这里插入图片描述

Input 输入包含多组数据,每组数据是一个以0 0结尾的整数对列表,表示了一条通道连接的两个房间的编号。房间的编号至少为1,且不超过100000。每两组数据之间有一个空行。
整个文件以两个-1结尾。

Output 对于输入的每一组数据,输出仅包括一行。如果该迷宫符合小希的思路,那么输出"Yes",否则输出"No"。

Sample Input
6 8 5 3 5 2 6 4 5 6 0 0

8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0

3 8 6 8 6 4 5 3 5 6 5 2 0 0

-1 -1
Sample Output
Yes
Yes
No

解题:利用并查集判断是否存在环,如果a和b已经在前面的输入中有了一条路径,当输入a和b时说明又再加一条路径,则此时不行
利用set来保存有哪些号码

注意:对于一组测试值输入0 0也要输出"Yes” /不要问为什么,就是这样规定的

#include<iostream>
#include<set>
using namespace std;
int parent[100005];
int find(int x)
{if(x != parent[x])parent[x] = find(parent[x]);return parent[x];
}
void uni(int x1,int x2)
{parent[x1] = x2;
}
int main()
{int a,b;while(cin >> a >> b){if(a == -1 && b == -1){break;}if(a == 0 && b == 0){cout << "Yes" << endl;continue;}set<int>shuzu;shuzu.insert(a);shuzu.insert(b);for(int i = 0; i < 100005;i++)parent[i] = i;int flag = true;int x1 = find(a);int x2 = find(b);if(x1 == x2)flag = false;else uni(x1,x2);while(cin >> a >> b){if(a == 0 && b == 0)break;else{shuzu.insert(a);shuzu.insert(b);int x3 = find(a);int x4 = find(b);if(x3 == x4)flag = false;else uni(x3,x4);}}set<int>::iterator it = shuzu.begin();int res = 0;while(it != shuzu.end()){if(parent[*it] == *it)res++;it++;} if(res != 1)flag = false;if(flag)cout << "Yes" << endl;else cout << "No" << endl;}
} 

http://www.ppmy.cn/news/283628.html

相关文章

小希的新工作

【问题描述】 小希最近找到了大公司的客户经理的新工作&#xff0c;每天工作时间为 L 分钟&#xff0c;他主要为 n 个固定的高端客人服务&#xff0c;第 i 个客人会在第 ti 分钟到来&#xff0c;他需要为其服务 li 分钟&#xff0c;在此期间不会有其他客人到来。 他喜欢在工作的…

小希练打字

实验八 字符串—小希练打字 【问题描述】 小希打字太慢了&#xff0c;因此他在苦练打字技巧。他用了一个教学 App&#xff0c;可以一个个显示自己打出来的英文单词。 当小希输入一个词时&#xff0c;他需要花0.2 秒输入第一个字母。而对于接下来的每个字母&#xff0c;如果在标…

小希与火车

【问题描述】 春节期间小希计划乘坐火车去旅行。开始时&#xff0c;火车位于位置1&#xff0c;目的地在位置L。火车的速度是1单位长度/分钟&#xff08;也就是第1分钟火车在位置1&#xff0c;第2分钟在位置2&#xff0c;等等&#xff09;。中国人过年都喜欢挂灯笼&#xff0c;在…

spark安装部署

spark安装部署 需要指导私信 所有节点安装scala&#xff0c;安装scala需要安装openjdk-8-jre&#xff08;当前用户如果没有sudo权限可将其加入sudo组里&#xff09;,以ubuntu2204-LTS为例&#xff1a; $ sudo apt update $ sudo apt-get install openjdk-8-jre-headless -y (红…

【Python 继承和多态】零基础也能轻松掌握的学习路线与参考资料

Python 继承和多态是面向对象编程中非常关键的概念。继承是一种创建新类的方法&#xff0c;通过继承一个已有的类来创建新类。而多态则是指不同的对象以不同的方式对同一消息作出响应的能力。在这篇文章中&#xff0c;我们将为您介绍 Python 继承和多态的学习路线&#xff0c;并…

i510400f配什么主板性能最好 i5 10400f配什么主板性能最好

酷睿i5-10400F基于祖传的14nm制程工艺&#xff0c;全新的LGA 1200接口设计&#xff0c;拥有6核12线程&#xff0c;默认主频2.9Ghz&#xff0c;最大睿频4.3Ghz&#xff0c;三级缓存为12MB&#xff0c;不支持超频&#xff0c;设计功耗65W&#xff0c;无内置核心显卡 i510400f组装…

i9 11900k配什么主板好 i911900k配什么显卡

i9-11900K为14nm工艺的最后一代产品&#xff0c;第12代将采用10纳米工艺。 i9 11900k组装电脑怎么搭配更适合这些点很重要http://www.adiannao.cn/du i9-11900K这次升级也是诚意满满。采用了新的架构&#xff0c;支持PCIE4.0&#xff0c;CPU提供了20个PCIE4.0通道&#xff0c;1…

计算机主板电池没电什么情况,主板电池没电了会出现什么情况

大家好&#xff0c;我是时间财富网智能客服时间君&#xff0c;上述问题将由我为大家进行解答。 以电脑为例&#xff0c;主板电池没电了会出现的情况有&#xff1a; 1、电脑每次开机&#xff0c;时间都会恢复到初始时间&#xff0c;也就是说&#xff0c;时间不能正常同步&#x…