4. 无向图的各连通分支
题目
求解无向图的各连通分支
输入:
第一行为图的节点数n(节点编号0至n-1,0<n<=10)
从第二行开始列出图的边,-1表示输入结束
输出:
输出每个连通分支的广度优先搜索序列(从连通分支的最小编号开始),不同分支以最小编号递增顺序列出
sample:
input:
8
0 5
5 2
4 5
5 6
6 2
3 7
-1
output:
0-5-2-4-6
1
3-7
C++代码
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>using namespace std;// 广度优先搜索函数
void bfs(int start, vector<bool>& visited, const vector<vector<int>>& adjList) {queue<int> q;q.push(start);visited[start] = true;while (!q.empty()) {int current = q.front();q.pop();cout << current; // 输出当前节点// 获取当前节点的所有相邻节点// 如果相邻节点未被访问过,则标记为已访问并加入队列for (int adj : adjList[current]) {if (!visited[adj]) {visited[adj] = true;q.push(adj);}}if (q.size()>0) cout << '-';}
}int main() {int n;cin >> n; // 读取节点数vector<vector<int>> adjList(n); // 邻接表vector<bool> visited(n, false); // 访问标记int u, v;while (true) {cin >> u;if (u == -1) break;cin >> v;adjList[u].push_back(v); // 添加边adjList[v].push_back(u); // 假设图是无向图,添加另一条边}// 对所有节点的邻接列表进行排序,以确保按节点编号升序搜索for (auto& edges : adjList) {sort(edges.begin(), edges.end());}// 对每个连通分支执行广度优先搜索for (int i = 0; i < n; ++i) {if (!visited[i]) {bfs(i, visited, adjList); // 执行广度优先搜索cout << endl;}}return 0;
}
相关文章:
4. 无向图的各连通分支
题目 求解无向图的各连通分支 输入: 第一行为图的节点数n(节点编号0至n-1,0<n<10) 从第二行开始列出图的边,-1表示输入结束 输出: 输出每个连通分支的广度优先搜索序列(从连通分支的最…...
《golang设计模式》第三部分·行为型模式-08-状态模式(State)
文章目录 1. 概念1.1 作用1.1 角色1.2 类图 2. 代码示例2.1 设计2.2 代码2.3 类图 1. 概念 1.1 作用 状态(State)指状态对象,用于封装上下文对象的特定状态行为,使得上下文对象在内部状态改变时能够改变其自身的行为。 1.1 角色…...
tp8 使用rabbitMQ(3)发布/订阅
发布/订阅 当我们想把一个消息,发送给 多个消费者的时候,我们把这种模式叫做发布/订阅模式,比如我们做两个消费者,其中一个消费者把消息写入磁盘中,别一个消费者把消息结果输出到屏幕上,就要用到发布订阅模…...
【nlp】3.4 Transformer论文复现:2. 编码器部分(规范化层、子层连接结构、编码器层)
3.4 Transformer论文复现:2. 编码器部分(规范化层、子层连接结构、编码器层) 2.6 规范化层2.6.1 规范化层的作用2.6.2 规范化层的代码实现2.6.3 规范化层总结2.7 子层连接结构2.7.1 子层连接结构2.7.2 子层连接结构的代码实现2.7.3 子层连接结构总结2.8 编码器层2.8.1 编码器…...
面试:ShardingSphere问题
文章目录 什么是ShardingSphere,它的主要功能是什么?ShardingSphere的核心模块有哪些?他们是如何工作的?ShardingSphere 的读写分离是如何实现的?如何配置ShardingSphere的数据分片策略?ShardingSphere支持…...
NX二次开发UF_CURVE_ask_offset_direction_2 函数介绍
文章作者:里海 来源网站:https://blog.csdn.net/WangPaiFeiXingYuan UF_CURVE_ask_offset_direction_2 Defined in: uf_curve.h int UF_CURVE_ask_offset_direction_2(UF_STRING_p_t input_curves, double offset_direction_vector [ 3 ] , double dra…...
【研究中】sql server权限用户设置23.11.26
--更新时间2023.11.26 21:30 负责人:jerrysuse DBAliCMSIF EXISTS (select * from sysobjects where namehkcms_user)--判断是否存在此表DROP TABLE hkcms_user CREATE TABLE hkcms_user (id int primary key identity(1, 1),username char(32) NOT N…...
java多线程一
1、什么是线程 线程(Thread)是一条程序内部的一条执行流程。 程序中如果只有一条执行流程,那这个程序就是单线程的程序。 2、什么是多线程 多线程(multithreading),是指从软件或者硬件上实现多个线程并发执…...
电脑技巧:电脑常见蓝屏、上不了网等故障及解决办法
目录 一、电脑蓝屏 常见原因1: 病毒木马 常见原因2: 安装了不兼容的软件 二、电脑不能上网 常见原因1: 新装系统无驱动 常见原因2: DNS服务器异常 常见原因3: 硬件问题 三、电脑没声音 常见原因1: 未安装驱动 常见原因2: 硬件故障 四、电脑屏幕不显示 常见原因1: 显…...
大语言模型损失函数详解
我们可以把语言模型分为两类: 自动回归式语言模型:自动回归式语言模型在本质上是单向的,也就是说,它只沿着一个方向阅读句子。正向(从左到右)预测;反向(从右到左)预测。…...
Spring Boot 3 集成 Knife4j
基础环境 SpringBoot : 3.0.6 Java: jdk-17.0.5 Maven: 3.6.1依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xs…...
BetaFlight模块设计之三十六:SoftSerial
BetaFlight模块设计之三十六:SoftSerial 1. 源由2. API接口2.1 openSoftSerial2.2 onSerialRxPinChange2.3 onSerialTimerOverflow2.4 processTxState2.5 processRxState 3. 辅助函数3.1 applyChangedBits3.2 extractAndStoreRxByte3.3 prepareForNextRxByte 4. 总结…...
PC访问华为昇腾开发板的摸索过程
作者:朱金灿 来源:clever101的专栏 为什么大多数人学不会人工智能编程?>>> 最近要折腾华为昇腾开发板(官方名称叫:Atlas 200I DK)。先是按照官方教程折腾:Atlas200DK环境部署。我发现…...
C++学习之路(六)C++ 实现简单的工具箱系统命令行应用 - 示例代码拆分讲解
简单的工具箱系统示例介绍: 这个示例展示了一个简单的工具箱框架,它涉及了几个关键概念和知识点: 面向对象编程 (OOP):使用了类和继承的概念。Tool 是一个纯虚类,CalculatorTool 和 FileReaderTool 是其派生类。 多态࿱…...
redis运维(十四) hash缓存案例
一 缓存案例 ① 需求 ② 个人理解 策略:不更新缓存,而是删除缓存大部分观点认为:1、做缓存不应该是去更新缓存,而是应该删除缓存2、然后由下个请求去缓存,发现不存在后再读取数据库,写入redis缓存 高并发场景下,到底先更新缓存还是先更…...
Rust UI开发(三):iced如何打开图片(对话框)并在窗口显示图片?
注:此文适合于对rust有一些了解的朋友 iced是一个跨平台的GUI库,用于为rust语言程序构建UI界面。 这是一个系列博文,本文是第三篇,前两篇的链接: 1、Rust UI开发(一):使用iced构建…...
网络爬虫(Python:Requests、Beautiful Soup笔记)
网络爬虫(Python:Requests、Beautiful Soup笔记) 网络协议简要介绍一。OSI参考模型二、TCP/IP参考模型对应关系TCP/IP各层实现的协议应用层传输层网络层 HTTP协议HTTP请求HTTP响应HTTP状态码 Requests(Python)Requests…...
【Kotlin】内联函数
文章目录 内联函数noinline: 避免参数被内联非局部返回使用标签实现Lambda非局部返回为什么要设计noinline crossinline具体化参数类型 Kotlin中的内联函数之所以被设计出来,主要是为了优化Kotlin支持Lambda表达式之后所带来的开销。然而,在Java中我们似…...
Unity技美35——再URP管线环境下,配置post后期效果插件(post processing)
前两年在我的unity文章第10篇写过,后效滤镜的使用,那时候大部分项目用的还是unity的基础管线,stander管线。 但是现在随着unity的发展,大部分项目都用了URO管线,甚至很多PC端用的都是高效果的HDRP管线,这就…...
Redis:持久化RDB和AOF
目录 概述RDB持久化流程指定备份文件的名称指定备份文件存放的目录触发RDB备份redis.conf 其他一些配置rdb的备份和恢复优缺点停止RDB AOF持久化流程AOF启动/修复/恢复AOF同步频率设置rewrite压缩原理触发机制重写流程no-appendfsync-on-rewrite 优缺点 如何选择 概述 Redis是…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
