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

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. 无向图的各连通分支

题目 求解无向图的各连通分支 输入&#xff1a; 第一行为图的节点数n&#xff08;节点编号0至n-1&#xff0c;0<n<10&#xff09; 从第二行开始列出图的边&#xff0c;-1表示输入结束 输出&#xff1a; 输出每个连通分支的广度优先搜索序列&#xff08;从连通分支的最…...

《golang设计模式》第三部分·行为型模式-08-状态模式(State)

文章目录 1. 概念1.1 作用1.1 角色1.2 类图 2. 代码示例2.1 设计2.2 代码2.3 类图 1. 概念 1.1 作用 状态&#xff08;State&#xff09;指状态对象&#xff0c;用于封装上下文对象的特定状态行为&#xff0c;使得上下文对象在内部状态改变时能够改变其自身的行为。 1.1 角色…...

tp8 使用rabbitMQ(3)发布/订阅

发布/订阅 当我们想把一个消息&#xff0c;发送给 多个消费者的时候&#xff0c;我们把这种模式叫做发布/订阅模式&#xff0c;比如我们做两个消费者&#xff0c;其中一个消费者把消息写入磁盘中&#xff0c;别一个消费者把消息结果输出到屏幕上&#xff0c;就要用到发布订阅模…...

【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&#xff0c;它的主要功能是什么&#xff1f;ShardingSphere的核心模块有哪些&#xff1f;他们是如何工作的&#xff1f;ShardingSphere 的读写分离是如何实现的&#xff1f;如何配置ShardingSphere的数据分片策略&#xff1f;ShardingSphere支持…...

NX二次开发UF_CURVE_ask_offset_direction_2 函数介绍

文章作者&#xff1a;里海 来源网站&#xff1a;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&#xff1a;30 负责人&#xff1a;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、什么是线程 线程&#xff08;Thread&#xff09;是一条程序内部的一条执行流程。 程序中如果只有一条执行流程&#xff0c;那这个程序就是单线程的程序。 2、什么是多线程 多线程&#xff08;multithreading&#xff09;&#xff0c;是指从软件或者硬件上实现多个线程并发执…...

电脑技巧:电脑常见蓝屏、上不了网等故障及解决办法

目录 一、电脑蓝屏 常见原因1: 病毒木马 常见原因2: 安装了不兼容的软件 二、电脑不能上网 常见原因1: 新装系统无驱动 常见原因2: DNS服务器异常 常见原因3: 硬件问题 三、电脑没声音 常见原因1: 未安装驱动 常见原因2: 硬件故障 四、电脑屏幕不显示 常见原因1: 显…...

大语言模型损失函数详解

我们可以把语言模型分为两类&#xff1a; 自动回归式语言模型&#xff1a;自动回归式语言模型在本质上是单向的&#xff0c;也就是说&#xff0c;它只沿着一个方向阅读句子。正向&#xff08;从左到右&#xff09;预测&#xff1b;反向&#xff08;从右到左&#xff09;预测。…...

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模块设计之三十六&#xff1a;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访问华为昇腾开发板的摸索过程

作者&#xff1a;朱金灿 来源&#xff1a;clever101的专栏 为什么大多数人学不会人工智能编程&#xff1f;>>> 最近要折腾华为昇腾开发板&#xff08;官方名称叫&#xff1a;Atlas 200I DK&#xff09;。先是按照官方教程折腾&#xff1a;Atlas200DK环境部署。我发现…...

C++学习之路(六)C++ 实现简单的工具箱系统命令行应用 - 示例代码拆分讲解

简单的工具箱系统示例介绍: 这个示例展示了一个简单的工具箱框架&#xff0c;它涉及了几个关键概念和知识点&#xff1a; 面向对象编程 (OOP)&#xff1a;使用了类和继承的概念。Tool 是一个纯虚类&#xff0c;CalculatorTool 和 FileReaderTool 是其派生类。 多态&#xff1…...

redis运维(十四) hash缓存案例

一 缓存案例 ① 需求 ② 个人理解 策略&#xff1a;不更新缓存&#xff0c;而是删除缓存大部分观点认为&#xff1a;1、做缓存不应该是去更新缓存,而是应该删除缓存2、然后由下个请求去缓存,发现不存在后再读取数据库,写入redis缓存 高并发场景下,到底先更新缓存还是先更…...

Rust UI开发(三):iced如何打开图片(对话框)并在窗口显示图片?

注&#xff1a;此文适合于对rust有一些了解的朋友 iced是一个跨平台的GUI库&#xff0c;用于为rust语言程序构建UI界面。 这是一个系列博文&#xff0c;本文是第三篇&#xff0c;前两篇的链接&#xff1a; 1、Rust UI开发&#xff08;一&#xff09;&#xff1a;使用iced构建…...

网络爬虫(Python:Requests、Beautiful Soup笔记)

网络爬虫&#xff08;Python&#xff1a;Requests、Beautiful Soup笔记&#xff09; 网络协议简要介绍一。OSI参考模型二、TCP/IP参考模型对应关系TCP/IP各层实现的协议应用层传输层网络层 HTTP协议HTTP请求HTTP响应HTTP状态码 Requests&#xff08;Python&#xff09;Requests…...

【Kotlin】内联函数

文章目录 内联函数noinline: 避免参数被内联非局部返回使用标签实现Lambda非局部返回为什么要设计noinline crossinline具体化参数类型 Kotlin中的内联函数之所以被设计出来&#xff0c;主要是为了优化Kotlin支持Lambda表达式之后所带来的开销。然而&#xff0c;在Java中我们似…...

Unity技美35——再URP管线环境下,配置post后期效果插件(post processing)

前两年在我的unity文章第10篇写过&#xff0c;后效滤镜的使用&#xff0c;那时候大部分项目用的还是unity的基础管线&#xff0c;stander管线。 但是现在随着unity的发展&#xff0c;大部分项目都用了URO管线&#xff0c;甚至很多PC端用的都是高效果的HDRP管线&#xff0c;这就…...

Redis:持久化RDB和AOF

目录 概述RDB持久化流程指定备份文件的名称指定备份文件存放的目录触发RDB备份redis.conf 其他一些配置rdb的备份和恢复优缺点停止RDB AOF持久化流程AOF启动/修复/恢复AOF同步频率设置rewrite压缩原理触发机制重写流程no-appendfsync-on-rewrite 优缺点 如何选择 概述 Redis是…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...