7-1 图图图
某城市有n个景点,部分景点之间有巴士免费来回接送。(1) 给定某个景点x,如果从这个景点出发坐一次免费巴士,可以到达多少个不同的景点?(2) 判断景点a是否可以通过免费巴士(可换乘)到达景点b;(3) 判断全部景点之间是否都可以通过免费巴士(可换乘)到达。
输入格式:
第一行是n, m值,分别代表景点数量,免费巴士线路的数量;1<=n,m<=100;
接下来有m行,每行有两个整数,分别代表第i(1<=i<=m)条免费巴士线路连接的两个景点编号;
接下来一行是景点x的编号;
最后一行是景点a, b 的编号(a!=b)。
说明:所有景点编号都在[1, n]范围内。
输出格式:
输出有三行:
第一行输出问题1的值;
第二行输出问题2的判断结果:YES 或者 NO;
第三行输出问题3的判断结果:YES 或者 NO.
输入样例:
在这里给出一组输入。例如:
5 4
1 3
1 2
4 5
1 4
1
1 5
输出样例:
在这里给出相应的输出。例如:
3
YES
YES
注意点:
1、设置vis[ ]数组记录顶点是否被访问过
2、处理完问题二后要重置vis[ ]数组
3、如果想vis[ ]顶点下标代表被访问顶点名称,则for循环范围是1~n
#include<iostream>
using namespace std;
const int Max =100;
int n,m;
int a[Max][Max]={0};
int vis[Max]={0};
bool search(int start,int end){ //判断两点是否有路径连通if(start==end) return true;vis[start]=1;for(int i=1;i<=n;i++){if(a[start][i]==1&&vis[i]==0){if(search(i,end)) return true;}}return false;
}
void DFS(int start) //从某一顶点进行深度搜索
{for(int i=1; i<=n; i++){if(!vis[i]&&a[start][i]){vis[i]=1;DFS(i);}}
}int main(){cin>>n>>m;for(int i=0;i<m;i++){int a1,a2;cin>>a1>>a2;a[a1][a2]=a[a2][a1]=1;}int x;cin>>x;int sum=0;for(int i=1;i<=n;i++){if(a[x][i]==1) sum++;}cout<<sum<<endl; // 问题1int start,end;cin>>start>>end;bool result=search(start,end);cout<<(result?"YES":"NO")<<endl;//问题2for(int i=1;i<=n;i++){ //重置vis数组vis[i]=0;}int cnt=0;for(int i=1; i<=n; i++) //判断图是否连通{if(vis[i]==0){DFS(i);cnt++;}} //问题3cout << ((cnt==1)?"YES" : "NO") << endl;
}
相关文章:
7-1 图图图
某城市有n个景点,部分景点之间有巴士免费来回接送。(1) 给定某个景点x,如果从这个景点出发坐一次免费巴士,可以到达多少个不同的景点?(2) 判断景点a是否可以通过免费巴士(可换乘)到达景点b;(3) …...
Java(多线程)
取水: 主部分: package a0506.Test3;import java.util.Random;public class Test3 {public static void main(String[] args) {Well2 well2new Well2(10);WellThread Zsnew WellThread("------张三------",well2,new Random().nextInt(5));W…...
程序员必备的7大神器,效率飞起!
我们都知道程序员在工作时,会经常遇到任务繁重的情况,为了提高效率,程序员们也会借助一些软件,那么哪些软件可以帮助程序员们提高工作效率呢? 整理不易,关注一波!! 1. Xftp 7 Xft…...
揭秘文件加密利器:24年度最值得信赖的5大加密软件评测
数据安全与隐私保护已成为我们每个人都必须面对的重要问题。 文件加密软件作为保障数据安全的关键工具,其重要性不言而喻。 在众多的加密软件中,哪些软件能够在保障数据安全的同时,又具备良好的易用性和稳定性呢? 本文将为您揭秘…...
【仪酷LabVIEW AI工具包案例】使用LabVIEW AI工具包+YOLOv5结合Dobot机械臂实现智能垃圾分类
🏡博客主页: virobotics(仪酷智能):LabVIEW深度学习、人工智能博主 🎄所属专栏:『仪酷LabVIEW AI工具包案例』 📑上期文章:『【YOLOv9】实战二:手把手教你使用TensorRT实现YOLOv…...
鸿蒙应用开发系列 EX篇:HarmonyOS应用开发者基础认证
文章目录 系列文章背景认证考试题库参考注意:题库会不定时的进行具备调整甚至整体轮换,此为2024.5月版本注意:题库中题目的选项每次都会随机顺序,请参考内容判断题单选题多选题系列文章 鸿蒙应用开发系列 篇一:鸿蒙系统概述 鸿蒙应用开发系列 篇二:鸿蒙系统开发工具与环…...
基于Linux中的 进程相关知识 综合讲解
目录 一、进程的基本概念 二、pid,ppid,fork函数 三、进程的状态讲解 四、进程的优先级 五、完结撒❀ 一、进程的基本概念 概念: ● 课本概念:程序的一个执行实例,正在执行的程序等 ● 内核观点:担当…...
前端高频面试题 5.08
事件委托 事件委托是前端开发中常用的一种优化性能和代码可维护性的方法,它基于DOM的事件冒泡机制。当一个元素触发事件时,这个事件会按照从顶层到底层的顺序传播,直到最底层的元素(通常是文档的根节点)。事件委托利用…...
python 的继承、封装和多态
1. 继承(Inheritance) 继承是面向对象编程中的一个重要概念,它允许一个类(子类)继承另一个类(父类)的属性和方法。子类可以重用父类的代码,同时也可以扩展或修改父类的行为。 常用…...
数智结合,智慧合同让法务管理发挥内在价值
在当今这个信息化、数字化飞速发展的时代,数据已成为企业重要的战略资源。法务管理作为企业内部控制和风险防范的重要环节,其重要性不言而喻。然而,传统的法务管理模式往往存在效率低下、信息孤岛、反应迟缓等问题。在这样的背景下࿰…...
Ubuntu 安装docker
1: 卸载旧版本 如果你曾经安装过旧版本的 Docker,首先需要卸载它们: sudo apt-get remove docker docker-engine docker.io containerd runc2: 安装依赖工具 安装一些必要的工具,以便后续的安装过程能够顺利进行: sudo apt-ge…...
【北京迅为】《iTOP-3588开发板快速烧写手册》-第8章 TF启动
RK3588是一款低功耗、高性能的处理器,适用于基于arm的PC和Edge计算设备、个人移动互联网设备等数字多媒体应用,RK3588支持8K视频编解码,内置GPU可以完全兼容OpenGLES 1.1、2.0和3.2。RK3588引入了新一代完全基于硬件的最大4800万像素ISP&…...
Helm 模板流程控制
Helm 的模板语言提供了多种控制结构,以允许模板作者根据条件逻辑生成模板内容。以下是 Helm 模板控制结构的核心内容总结: 控制结构 Helm 模板支持以下控制结构: if/else:用于创建条件语句,根据给定的条件包含或排除…...
Kansformer?变形金刚来自过去的新敌人
1.前言 多层感知器(MLPs),也被称为全连接前馈神经网络,是当今深度学习模型的基础组成部分。 MLPs在机器学习中扮演着至关重要的角色,因为它们是用于近似非线性函数的默认模型,这得益于通用近似定理所保证的表达能力。然而,MLPs真的是我们能构建的最佳非线性回归器吗?尽管ML…...
今晚 19:00 | 从这两个问题入手,带你了解数据要素相关税务问题
五一假期已经结束,返工后当然是继续劳动啦~数据要素系列直播《星光对话》第三期也将在今晚19:00,继续跟大家见面。 本期直播,依然由 星光数智咨询总监 刘靖 主讲,带来:《数据要素相关税务问题解读》。 主要围绕两个问题…...
《QT实用小工具·五十一》带动画的 CheckBox
1、概述 源码放在文章末尾 该项目实现了带动画效果的多选框,鼠标放在上面或者选中都会呈现炫酷的动画效果,demo演示如下: 项目部分代码如下所示: #ifndef LINEARCHECKBOX_H #define LINEARCHECKBOX_H#include <QCheckBox> …...
PDT(police digital trunking )警用数字集群射频指标及测试方法
天线端口----测试传导 机箱端口----测试辐射 基本概念 传导测试方法 VBW3RBW 仪器设置 辐射测试方法...
《尿不湿级》STM32 F103C8T6最小系统板搭建(五)BOOT
一、BOOT是什么? 大多数初学者第一次接触BOOT总是对这个词感到不解,从哪冒出一个奇奇怪怪的东西还要接跳线帽,为什么要配置它才能进行串口程序的下载?为什么不正确配置会导致单片机无法正常启动…… boot,及物动词&…...
Java项目:基于SSM框架实现的高校专业信息管理系统设计与实现(ssm+B/S架构+源码+数据库+毕业论文+PPT+开题报告)
一、项目简介 本项目是一套基于SSM框架实现的高校专业信息管理系统 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,eclipse或者idea 确保可以运行! 该系统功能完善、界面美观、操作简单、…...
linux高性能服务器-线程池实现
文章目录 定义应用场景任务类型线程数量数据结构设计:任务设计:队列设计:线程池设计 接口设计 定义 线程池属于生产消费模型,管理维持固定数量线程的池式结构,避免线程频繁的创建和销毁 应用场景 当一类任务耗时&am…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
