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…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
