当前位置: 首页 > news >正文

小希的迷宫

目录

描述

输入

输出

样例输入

样例~~输出~~

思路

code


描述

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

输入

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

输出

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

样例输入
6 8  5 3  5 2  6 4
5 6  0 08 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 03 8  6 8  6 4
5 3  5 6  5 2  0 0-1 -1
样例输出
Yes
Yes
No

思路

构成一个无向图,判断这个图有没有回路也就是判断这个图是不是一棵树,在输入阶段中,我们要注意一个小细节,一开始在输入“0 0”,输出应该为Yes

判断无向图是否为一颗树,两种方法

1、树的边数+1=节点数,并且树一定没有环

2、并查集法,若图中存在环,必然存在一条边的两个点,在判断他们所属的集合时,会出现相等的情况

我们用第2种方法

code

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
const int N = 1e5 + 10;
int pre[N], flag[N];//flag为房间是否访问过,0代表没访问过,1代表访问过
int find(int x) {return pre[x] == x ? x : pre[x] = find(pre[x]);
}
void merge(int x, int y) {pre[find(x)] = find(y);
}
void init() {for (int i = 0; i < N; i++) {pre[i] = i;}
}
int main()
{int x, y;while (cin >> x >> y && x != -1) {if (!x && !y) { //对一开始为0 0 输入,要输出Yescout << "Yes" << endl;continue;}init();//初始化为将每个房间所在集合为自己的房间号memset(flag, 0, sizeof(flag));//c++memset头文件为stringflag[x] = flag[y] = 1;merge(x, y);int flag1 = 1;//标记是否存在回路if (x == y) flag1 = 0;
//x==y 代表两个房间为一个房间,当前状态不合法,
//如果一个房间自己相连,则意味着有两条或两条以上的路径能够到达同一个房间while (cin >> x >> y && x) {if (find(x) == find(y))flag1 = 0;//存在回路flag[x] = flag[y] = 1;merge(x, y);}if (!flag1) { cout << "No" << endl; continue; }set<int> s;for (int i = 1; i < N; i++) {if (!flag[i]) continue;s.insert(find(i));}cout << ((int)s.size() > 1 ? "No" : "Yes") << endl;}return 0;
}

相关文章:

小希的迷宫

目录 描述 输入 输出 样例输入 样例~~输出~~ 思路 code 描述 Gardon的迷宫城堡小希玩了很久&#xff08;见Problem B&#xff09;&#xff0c;现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样&#xff0c;首先她认为所有的通道都应该是双向连通的&…...

MySQL索引剖析【了解背后的数据结构】

文章目录 常用索引概念聚簇索引 &#x1f389;非聚簇索引&#xff08;二级索引&#xff09; 数据结构选择Hash结构 ⭐️有序数组二叉搜索树AVL树&#xff08;平衡二叉搜索树&#xff09;B-Tree&#xff08;多路平衡查找树&#xff09;BTree ⭐️ MySQL中索引的实现InnoDB 索引实…...

004——内存映射(基于鸿蒙和I.MAX6ULL)

目录 一、 ARM架构内存映射模型 1.1 页表项 1.2 一级页表映射过程 1.3 二级页表映射过程 1.4 cache 和 buffer 二、 鸿蒙内存映射代码学习 三、 为板子编写内存映射代码 3.1 内存地址范围 3.2 设备地址范围 一、 ARM架构内存映射模型 &#xff08;以前我以为页表机制…...

150 Linux C++ 通讯架构实战6 服务器程序目录规划,makefile编写

从无到有产生这套 通讯架构源代码【项目/工程】 一&#xff0c;服务器程序目录规划 一个完整的项目 肯定会有多个源文件&#xff0c;头文件&#xff0c;会分别存放到多个目录&#xff1b; 我们这里要规划项目的目录结构&#xff1b; 注意&#xff1a;不固安是目录还是文件&am…...

OpenCV支持哪些类型的文件格式读写?

OpenCV支持多种类型的文件格式读写&#xff0c;包括但不限于以下格式&#xff1a; Windows位图文件&#xff1a;包括BMP和DIB格式。JPEG文件&#xff1a;支持JPEG、JPG和JPE三种扩展名。便携式网络图片&#xff1a;即PNG格式。便携式图像格式&#xff1a;包括PBM、PGM和PPM三种…...

数据库中使用IN操作效率问题

1. IN操作的基本概念 IN操作符在SQL中用于指定某个字段的值是否匹配列表中的任何值。这是一个条件操作符&#xff0c;用于在WHERE子句中过滤记录。 SQL语法示例&#xff1a; SELECT * FROM table_name WHERE column_name IN (value1, value2, ...); 2. IN操作的效率问题 当…...

unity学习(67)——控制器Joystick Pack方向

1.轮盘直接复制一个拖到右边就ok了&#xff0c;轮盘上是有脚本的。&#xff08;只复制&#xff09; 2.上面的显示窗也可以复制&#xff0c;但是要绑定对应的轮盘&#xff08;unity中修改变量&#xff09;&#xff0c;显示窗上是有脚本的。&#xff08;复制改变量&#xff09; 3…...

MATLAB的使用(一)

一&#xff0c;MATLAB的编程特点 a,语法高度简化&#xff1b; b,脚本式解释型语言&#xff1b; c,针对矩阵的高性能运算&#xff1b; d,丰富的函数工具箱支持&#xff1b; e,通过matlab本体构建跨平台&#xff1b; 二&#xff0c;MATLAB的界面 工具栏:提供快捷操作编辑器…...

JMeter并发工具的使用

视频地址&#xff1a;Jmeter安装教程01_Jmeter之安装以及环境变量配置_哔哩哔哩_bilibili 一、JMeter是什么 JMeter是一款免安装包&#xff0c;官网下载好后直接解压缩并配置好环境变量就可以使用。 环境变量配置可参考&#xff1a;https://www.cnblogs.com/liulinghua90/p/…...

基于springboot+vue的毕业就业信息管理系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…...

有什么小程序适合个人开发?

在这个信息爆炸的时代&#xff0c;小程序已经成为了我们生活中的一部分。无论是出行、购物还是娱乐&#xff0c;小程序都能为我们提供便捷的服务。对于个人开发者来说&#xff0c;开发一个小程序不仅可以锻炼自己的技术能力&#xff0c;还可以为他人提供便利&#xff0c;甚至有…...

【ARXIV2402】MambaIR

这个工作首次将 Mamba 引入到图像修复任务&#xff0c;关于为什么 Mamba 可以用于图像修复&#xff0c;作者有非常详细的解释&#xff1a;一路向北&#xff1a;性能超越SwinIR&#xff01;MambaIR: 基于Mamba的图像复原基准模型 作者认为Mamba可以理解为RNN和CNN的结合&#xf…...

【计算机网络篇】数据链路层(3)差错检测

文章目录 &#x1f95a;误码&#x1f354;两种常见的检错技术⭐奇偶校验⭐循环冗余校验&#x1f388;例子 &#x1f95a;误码 误码首先介绍误码的相关概念 &#x1f354;两种常见的检错技术 ⭐奇偶校验 奇校验是在待发送的数据后面添加1个校验位&#xff0c;使得添加该校验…...

软件配置管理计划

1. 配置管理目标 本软件配置管理计划的目标在于确保软件开发生命周期内的所有配置项&#xff08;CI&#xff09;都得到适当的标识、控制、版本管理和追踪。通过实施有效的配置管理&#xff0c;我们的目标是&#xff1a; 保持配置项的一致性和完整性。确保配置项的可追溯性。减…...

嵌入式备考错题汇总

若某条无条件转移汇编指令采用直接寻址&#xff0c;则该指令的功能是将指令中的地址码送入()。 A.PC(程序计数器) B.AR(地址寄存器) C.AC(累加器) D.ALU(算术逻辑运算单元) 解析&#xff1a;选A,直接寻址是指操作数存放在内存单元中&#xff0c;指令中直接给出操作数所在存储单…...

38 mars3d 对接地图图层 绘制点线面员

前言 这里主要是展示一下 mars3d 的一个基础的使用 主要是设计 接入地图服务器的 卫星地图, 普通的二维地图, 增加地区标记 基础绘制 点线面园 等等 测试用例 <template><div style"width: 1920px; height:1080px;"><div class"mars3dClas…...

什么是Webhook 和 HTTP Endpoint?

Webhook 和 HTTP Endpoint 都是基于HTTP协议的网络通信概念&#xff0c;但它们在使用场景和目的上有所不同。 Webhook Webhook 是一种允许一个应用程序提供实时信息给其他应用程序的方法&#xff0c;这种通信是基于HTTP的“回调”或“钩子”。Webhook 通常被用来在一种服务上…...

小程序跨端组件库 Mpx-cube-ui 开源:助力高效业务开发与主题定制

Mpx-cube-ui 是一款基于 Mpx 小程序框架的移动端基础组件库&#xff0c;一份源码可以跨端输出所有小程序平台及 Web&#xff0c;同时具备良好的拓展能力和可定制化的能力来帮助你快速构建 Mpx 应用项目。 Mpx-cube-ui 提供了灵活配置的主题定制能力&#xff0c;在组件设计开发阶…...

GDC期间LayaAir启动全球化战略

3 月 18 日至 3 月 22 日&#xff0c;一年一度的游戏开发者大会&#xff08;GDC&#xff09;在美国旧金山举行。在此期间&#xff0c;Layabox宣布LayaAir引擎启动全球扩张战略&#xff0c;这标志着引擎将步入快速发展的新阶段。此举旨在利用公司先进的3D引擎技术&#xff0c;将…...

人工智能之Tensorflow批标准化

批标准化&#xff08;Batch Normalization,BN&#xff09;是为了克服神经网络层数加深导致难以训练而诞生的。 随着神经网络的深度加深&#xff0c;训练会越来越困难&#xff0c;收敛速度会很慢&#xff0c;常常会导致梯度消失问题。梯度消失问题是在神经网络中&#xff0c;当前…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...