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

7-1 列出连通集

news 来源：原创 2025/8/21 9:23:49

作者陈越

单位浙江大学

给定一个有 n 个顶点和 m 条边的无向图，请用深度优先遍历（DFS）和广度优先遍历（BFS）分别列出其所有的连通集。假设顶点从 0 到 n−1 编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式:

输入第 1 行给出 2 个整数 n (0<n≤10) 和 m，分别是图的顶点数和边数。随后 m 行，每行给出一条边的两个端点。每行中的数字之间用 1 空格分隔。

输出格式:

按照"{ v1 v2 ... vk }"的格式，每行输出一个连通集。先输出 DFS 的结果，再输出 BFS 的结果。

输入样例:
8 6
0 7
0 1
2 0
4 1
2 4
3 5
输出样例:
{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }
代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include<bits/stdc++.h>
using namespace std;
bool G[11][11],st[11];
int n,m;
int path[11],cnt,idx;
queue<int>q;
void dfs(int idx){path[cnt++]=idx;st[idx]=true;for(int i=0;i<n;i++)if(st[i]==false&&G[idx][i])dfs(i);
}
void bfs(int idx){q.push(idx);st[idx]=true;//压入就要设置为已遍历while(q.size()){int t=q.front();q.pop();path[cnt++]=t;for(int i=0;i<n;i++)if(st[i]==false&&G[t][i]){//监测t的邻居iq.push(i);st[i]=true;//必须在压入的时候就设置为遍历过，等到取出再设置可能已经压入多次}}
}
int main(){cin>>n>>m;for(int i=0;i<m;i++){int a,b;cin>>a>>b;G[a][b]=1;G[b][a]=1;}idx=cnt=0;while(1){while(st[idx])idx++;if(idx==n)break;cnt=0;dfs(idx);cout<<"{ ";for(int i=0;i<cnt;i++)cout<<path[i]<<" ";cout<<"}"<<endl;}idx=cnt=0;fill(st,st+n,false);while(1){while(st[idx])idx++;if(idx==n)break;cnt=0;bfs(idx);cout<<"{ ";for(int i=0;i<cnt;i++)cout<<path[i]<<" ";cout<<"}"<<endl;}return 0;
}

7-1 列出连通集

作者陈越单位浙江大学给定一个有 n 个顶点和 m 条边的无向图，请用深度优先遍历（DFS）和广度优先遍历（BFS）分别列出其所有的连通集。假设顶点从 0 到 n−1 编号。进行搜索时，假设我们总是从编号最小的顶点…...

编程日记 2025/8/21 9:23:49

XML Schema 指示器

XML Schema 指示器引言 XML Schema 是一种用于定义 XML 文档结构的语言，它能够确保 XML 文档的合法性。在 XML 文档的解析和应用中，XML Schema 指示器（XML Schema Indicator）扮演着至关重要的角色。本文将详细介绍 XML Schema 指示器的概念、作用、应用场景以及如何使用…...

编程日记 2025/8/18 0:58:58

Linux内核中TCP协议栈的实现：tcp_close函数的深度剖析

引言 TCP（传输控制协议）作为互联网协议族中的核心协议之一，负责在不可靠的网络层之上提供可靠的、面向连接的字节流服务。Linux内核中的TCP协议栈实现了TCP协议的全部功能，包括连接建立、数据传输、流量控制、拥塞控制以及连接关闭等。本文将深入分析Linux内核中tcp_close…...

编程日记 2025/8/22 9:14:57

17-产品经理-创建发布

点击“发布”-“创建发布”。填写发布名称，选择测试的版本。还可以设置此次发布是否为“里程碑”。点击“保存”后，进入该发布详情页面。需要为此次发布关联需求、已解决BUG、以及遗留BUG。可以通过设置条件，进行“搜索”，然后批…...

编程日记 2025/8/21 16:16:37

了解Spring的统一功能

目录一、统一数据返回格式 1.引入统一数据返回格式 2.学习使用统一数据返回格式 support方法 beforeBodyWrite方法统一数据返回格式具体逻辑使用统一数据返回格式存在的问题解决方法： 统一数据返回格式的优点统一数据返回格式代码实现（包含了…...

编程日记 2025/8/22 9:16:42

123213

根据道路在道路网的地位、交通功能、对沿线的服务功能划分可分为快速路、主干路、次干路及支路快速路完全为交通功能服务, 主干路以交通功能为主, 次干路是城市区域性的交通干道，为区域交通集散服务，兼有服务功能，结合主干路组成干路网 …...

编程日记 2025/8/21 21:02:01

通过 axios 请求回来的 HTML 字符串渲染到 Vue 界面上并添加样式

1. 通过 axios 获取数据使用 axios 发起请求，获取返回的 HTML 字符串数据。 2. 在 Vue 中处理和渲染数据由于 HTML 字符串中可能包含一些标签和样式，直接插入到 Vue 的模板中可能会导致样式问题。可以通过以下方式处理： 方法一&#xf…...

编程日记 2025/8/22 9:18:01

P1162 填涂颜色（BFS）

题目描述由数字 0 组成的方阵中，有一任意形状的由数字 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2。例如：66 的方阵（n6），涂色前和涂色后的方阵如下： 如果从某个 0 出发，只向上下…...

编程日记 2025/8/21 5:11:42

【笔记】VS中C#类库项目引用另一个类库项目的方法

VS中C#类库项目引用另一个类库项目的方法在 C# 开发中，有时我们需要在一个类库项目中引用另一个类库项目，但另一个项目可能尚未编译成 DLL。在这种情况下，我们仍然可以通过 Visual Studio 提供的项目引用功能进行依赖管理。 🎯 …...

编程日记 2025/8/17 23:32:16

进程内存分布--之smaps呈现memory-layout.cpp内存分布

上一篇介绍了：进程内存分布--之单线程代码来内存分布呈现memory-layout.cpp 这里我们使用smaps将更加形象的的体现内存分布，smaps文件是Linux的proc文件系统提供的一种可以查看内存资源使用情况的方法,Linux系统中运行的库、堆、栈等信息都可在smaps中查…...

编程日记 2025/8/17 23:05:30

再看自适应RAG方法：SEAKR|PIKE-RAG|DeepRAG

当大语言模型开始"怀疑人生"：一场关于知识检索的AI内心戏各位看官，今天我们要聊一个AI界的"哲学难题"——当大语言模型突然意识到自己可能是个"半瓶子醋"，会发生什么奇妙反应？想象一下这个场景：某天深夜，ChatGPT正对着用户提问"如…...

编程日记 2025/8/22 9:18:03

DNS服务（Linux）

DNS 介绍 dns，Domain Name Server，它的作用是将域名解析为 IP 地址，或者将IP地址解析为域名。这需要运行在三层和四层，也就是说它需要使用 TCP 或 UDP 协议，并且需要绑定端口，53。在使用时先通过 UDP 去…...

编程日记 2025/8/17 22:17:41

探秘PythonJSON解析深度剖析json.loads处理嵌套JSON字符串的奥秘

哈喽，大家好，我是木头左！在当今数字化时代，数据以各种格式呈现，而JSON（JavaScript Object Notation）作为一种轻量级的数据交换格式，在众多领域广泛应用。Python作为一门强大的编程语言，其内置的json模块为处理JSON数据提供了便捷的方法。然而，当遇到像{"name&q…...

编程日记 2025/8/17 22:18:02

Day7 FIFO与鼠标控制

文章目录 1. harib04a例程（获取按键编码）2. harib04b例程（加快中断处理）3. harib04c例程（FIFO缓冲区）4. harib04d例程（改善FIFO缓冲区）5. harib04e例程（整理FIFO缓冲区&a…...

编程日记 2025/8/22 9:16:43

软件工程第一章习题

第1章软件与软件工程 1.选择题 (1)下列说法中正确的是( ）o A.20世纪50年代提出了软件工程的概念 B.20世纪60年代提出了软件工程的概念 C.20世纪70年代出现了客户机/服务器技术 D.20世纪80年代软件工程学科达到成熟 (2)软件危机的主要原因是( Do B.软件生产…...

编程日记 2025/8/22 5:12:02

Ollama 手动高速下载Win/Linux/Mac安装包及安装方法

前言 Ollama下载速度太慢，按这个方式，速度嘎嘎的快----下载地址手动安装如果要从以前的版本升级，则应删除旧库。比如：sudo rm -rf /usr/lib/ollama 解压 tar -C /usr -xzf ollama-linux-amd64.tgz # 解压到/usr文件夹# 如…...

编程日记 2025/8/22 9:17:16

Jmeter+Jenkins+Ant自动化持续集成环境搭建

一、安装准备 1.JDK:jdk-8u121-windows-x64 2.jmeter工具：apache-jmeter-2.13 3.ANT工具：apache-ant-1.9.7-bin 4.jenkins工具：jenkins-2.32.2 二、软件安装 1.JDK的安装 >双击JDK安装包，选择安装路径（本人是…...

编程日记 2025/8/22 9:18:43

【11】Redis快速安装与Golang实战指南

文章目录 1 Redis 基础与安装部署1.1 Redis 核心特性解析1.2 Docker Compose 快速部署1.3 Redis 本地快速部署 2 Golang 与 Redis 集成实战2.1 环境准备与依赖安装2.2 核心操作与数据结构实践2.2.1 基础键值操作2.2.2 哈希结构存储用户信息 3 生产级应用场景实战3.1 分布式锁实…...

编程日记 2025/8/22 9:18:45

ISP算法.红外图像增强

在图像处理领域，常见的图像处理一般都是白光相机，实际红外相机也是常见的一种相机，它可以用来对发热的东西进行成像，也可以作为白光相机夜晚不可见的一种辅助手段，为白光相机赋能夜视能力。红外相机的成像原理在于辐射…...

编程日记 2025/8/21 19:06:55

Spring Boot中使用RedisTemplate操作Redis的几种数据类型详解

Redis作为高性能的键值存储系统，在现代Java应用中扮演着重要角色。Spring Boot通过RedisTemplate为开发者提供了便捷的Redis操作方式。本文将详细介绍如何使用RedisTemplate操作Redis的五种主要数据类型。一、RedisTemplate简介 RedisTemplate是Spring Data Redi…...

编程日记 2025/8/22 9:14:58

大数据与人工智能之大数据架构（Hadoop、Spark、Flink）

一、核心特性与架构设计 1. Hadoop：分布式批处理的基石核心组件： HDFS：分布式文件系统，支持大规模数据存储。MapReduce：基于“分而治之”的批处理模型，适合离线分析。架构特点： 批处理主导&…...

编程日记 2025/8/22 9:17:16

VSCode中Marp插件

VSCode神级插件Marp，用Markdown来做PPT 优秀教程：https://zhuanlan.zhihu.com/p/582872955...

编程日记 2025/8/17 22:18:40

C++20 数学常数：＜numbers＞头文件的革新

文章目录一、<numbers> 头文件中的数学常数二、使用示例三、优势与应用场景（一）提高代码可读性（二）提高精度（三）适用于多种数据类型（四）简化数学计算四、总结 C20 标准引入了…...

编程日记 2025/8/22 2:05:48

OpenCV--图像平滑处理

在数字图像处理领域，图像平滑处理是一项极为重要的技术，广泛应用于计算机视觉、医学影像分析、安防监控等多个领域。在 OpenCV 这一强大的计算机视觉库的助力下，我们能便捷地实现多种图像平滑算法。本文将深入探讨图像平滑的原理，…...

编程日记 2025/8/17 22:17:44

【KMP】P7114 [NOIP2020] 字符串匹配|省选-

本文涉及知识点较难理解的字符串查找算法KMP P7114 [NOIP2020] 字符串匹配题目描述小 C 学习完了字符串匹配的相关内容，现在他正在做一道习题。对于一个字符串 S S S，题目要求他找到 S S S 的所有具有下列形式的拆分方案数： S A …...

编程日记 2025/8/17 22:19:40

C++20 统一容器擦除：std::erase 和 std::erase_if

文章目录一、std::erase 的用法1.1 语法1.2 参数1.3 返回值1.4 示例二、std::erase_if 的用法2.1 语法2.2 参数2.3 返回值2.4 示例三、优势与应用场景3.1 统一的接口3.2 简化代码3.3 适用范围广四、总结 C20 引入了两个非常实用的函数模板： std::erase 和 std…...

编程日记 2025/8/17 22:19:18

阿里云oss视频苹果端无法播放问题记录

记录一下苹果端视频不可以播放的原因. 看了一下其他视频可以正常播放,但是今天客户发来的视频无法正常播放.咨询过阿里云售后给出的原因是编码格式过高. 需要调整编码格式为:baseline, 下面记录如何使用ffmpeg修改视频的编码格式. 下载文件(可从官方下载) 配置环境变量(系统变…...

编程日记 2025/8/22 1:22:16

10-MySQL-性能优化思路

1、优化思路当我们发现了一个慢SQL的问题的时候，需要做性能优化，一般我们是为了提高SQL查询更快，一个查询的流程由下图的各环节组成，每个环节都会消耗时间，要减少消耗时候需要从各个环节都分析一遍。 2 连接配置优化…...

编程日记 2025/8/17 23:51:34

Postman之参数化详解

🍅 点击文末小卡片 ，免费获取软件测试全套资料，资料在手，涨薪更快小伙伴们，好久不见呀，今天呢笔者想和大家聊聊postman参数化，在接口测试中，部分参数每次发送请求是唯一的数值&a…...

编程日记 2025/8/17 23:14:52

【c++深入系列】：类和对象详解（下）

🔥 本文专栏：c 🌸作者主页：努力努力再努力wz 💪 今日博客励志语录： 你的人生剧本，不是父母的续集，不是子女的前传，更不是朋友的外传——你是自己故事的主角 ★★★ 本文前…...

编程日记 2025/8/21 22:33:04

浅谈「分词」：原理 + 方案对比 + 最佳实践

在文本搜索、自然语言处理、智能推荐等场景中，「分词」是一个基础但至关重要的技术点。无论是用数据库做模糊查询，还是构建搜索引擎，分词都是提高效率和准确度的核心手段。 🔍 一、什么是分词？ 分词（Tok…...

编程日记 2025/8/17 22:18:39

第十八：GC 垃圾回收

2.1 三色标记# 灰色：对象已被标记，但这个对象包含的子对象未标记黑色：对象已被标记，且这个对象包含的子对象也已标记，gcmarkBits对应的位为1（该对象不会在本次GC中被清理）白色：对象…...

编程日记 2025/8/17 1:58:15

【微机及接口技术】- 第七章可编程定时/计数器

文章目录第一节定时/计数器的概述一、定时与计数二、定时方法第二节可编程定时/计数器8254一、8254-2的基本功能二、8254的内部结构和外部引脚三、8254 的工作方式1. 方式0：计数到零产生中断方式2. 方式1：硬件可重触发单稳方式3. 方式2：速…...

编程日记 2025/8/20 19:42:25

MES生产工单管理系统，Java+Vue，含源码与文档，实现生产工单全流程管理，提升制造执行效率与精准度

前言： MES生产工单管理系统是制造业数字化转型的核心工具，通过集成生产、数据、库存等模块，实现全流程数字化管理。以下是对各核心功能的详细解析： 一、生产管理工单全生命周期管理创建与派发：根据销售订单或生产计…...

编程日记 2025/8/20 18:40:07

【区块链安全 | 第三十五篇】溢出漏洞

文章目录溢出上溢示例溢出漏洞溢出示例漏洞代码代码审计1. deposit 函数2. increaseLockTime 函数攻击代码攻击过程总结修复建议审计思路溢出算术溢出（Arithmetic Overflow），简称溢出（Overflow），通常分…...

编程日记 2025/8/17 23:59:19

设备上内置了一块声卡，出于某些原因我希望禁用他。通过arecord -l可以查看到该设备 $ arecord -l **** List of CAPTURE Hardware Devices **** card 0: Device [USB PnP Sound Device], device 0: USB Audio [USB Audio]Subdevices: 1/1Subdevice #0: subdevice…...

编程日记 2025/8/19 4:17:57

设计模式 Day 4：观察者模式（Observer Pattern）深度解析

在经历了前三天的对象创建型设计模式学习之后，今天我们开始进入行为型设计模式的探索之旅。行为型模式聚焦于对象之间的通信机制与协作方式，其中最经典且应用最广泛的就是——观察者模式（Observer Pattern）。本文将用8000字篇幅&a…...

编程日记 2025/8/20 16:27:42

`QTabWidget` 的标签页头设置样式，可以通过在 QSS 文件中定义 `QTabBar::tab` 的样式

要为 QTabWidget 的标签页头设置样式，可以通过在 QSS 文件中定义 QTabBar::tab 的样式来实现。以下是完整的代码示例和 QSS 文件内容，展示如何为标签页头设置背景颜色、文本颜色、悬停效果和选中效果。 ### **代码示例** cpp #include <QApplication…...

编程日记 2025/8/22 8:00:38

低代码开发革命：用 ZKmall开源商城可视化逻辑编排实现业务流程再造

ZKmall开源商城通过可视化逻辑编排引擎与低代码开发范式，重新定义了企业级电商业务流程的构建与优化方式。本文将从技术架构、核心能力、实践案例及行业价值等维度，解析其如何以"低代码流程引擎"组合拳实现业务流程再造的革命性突破。一、低代…...

编程日记 2025/8/19 18:15:00

CAN外设

目录 1. CAN外设结构 1.1 CAN外设发送流程 1.2 CAN外设接收流程 1.3 发送接受配置位 2. CAN外设过滤器 2.1 过滤器配置 2.2 测试模式 2.3 工作模式 2.4 过滤器对应中断 2.5 错误处理和离线恢复 1. CAN外设结构以STM32F103为例。以下是它的内部结构框图。其具体发…...

编程日记 2025/8/21 17:17:39

（七）安卓开发中的状态列表图形（StateListDrawable）详解

在安卓开发中，**状态列表图形（StateListDrawable）**是一种非常实用的资源，它允许开发者根据视图的不同状态（如按下、聚焦、选中等）来动态显示不同的图像或颜色。这种机制在创建交互式用户界面时尤为重要&am…...

编程日记 2025/8/20 15:00:35

2023年蓝桥杯第十四届CC++大学B组真题及代码

目录 1A：日期统计解析代码_暴力_正解 2B：01串的熵解析代码_暴力_正解 3C：冶炼金属解析代码_暴力_正解 4D：飞机降落解析代码_暴力dfs_正解 5E：接龙数列解析代码_dp_正解 6F：岛屿个数解析代…...

编程日记 2025/8/17 23:41:52

odo18实施——销售-仓库-采购-制造-制造外包-整个流程自动化单据功能的演示教程

安装模块安装销售、库存、采购、制造模块 2.开启外包功能在进入制造应用点击配置—>设置勾选外包，点击保存添加信息一、添加客户信息点击到销售应用点击订单—>客户点击新建创建客户1，及其他客户相关信息，点…...

编程日记 2025/8/17 22:19:50

c++造轮子之REACTOR实战

本文实现的为单reactor 多线程(base) 非核心库 InetAddress 这个库简单而言无疑是设置ip地址和端口 class InetAddress { public:struct sockaddr_in addr;socklen_t addr_len;InetAddress();InetAddress(const char* ip, uint16_t port);~InetAddress(); };具体而言: Ine…...

编程日记 2025/8/18 0:21:01

【Easylive】Elasticsearch搜索组件详解

【Easylive】项目常见问题解答（自用&持续更新中…） 汇总版一、Elasticsearch基础介绍 Elasticsearch(简称ES)是一个分布式、RESTful风格的搜索和分析引擎，基于Apache Lucene构建。在视频平台中，它主要用于： 全…...

编程日记 2025/8/19 10:09:23

基于AT89C51单片机的加减乘除液晶计算机设计

点击链接获取Keil源码与Project Backups仿真图： https://download.csdn.net/download/qq_64505944/90574816?spm1001.2014.3001.5503 功能介绍： 可进行最高四位数的加减乘除运算，除法运算保留小数点后四位；4*4矩阵按键输入&…...

编程日记 2025/8/20 2:26:54

先进制造aps专题三十三开源aps产品，frepple和dream对比分析

开源的两个aps产品，frepple和dream对比分析 frepple开源的基本不能用，第一它甘特图没开源，而且甘特图不允许你手工个修改，你想把它当成手工甘特图用也不行，第二，算法强制倒排，很少企业是倒排 …...

编程日记 2025/8/21 14:18:06

Vue3.2 项目打包成 Electron 桌面应用

本文将详细介绍如何将基于 Vue3.2 的项目打包成 Electron 桌面应用。通过结合 Electron 和 Vue CLI 工具链，可以轻松实现跨平台桌面应用的开发与发布。 1. 项目结构说明项目主要分为以下几个部分： electron/main.js：Electron 主进程文件。…...

编程日记 2025/8/17 23:53:51

第16届蓝桥杯单片机模拟试题Ⅰ

试题代码 sys.h #ifndef __SYS_H__ #define __SYS_H__#include <STC15F2K60S2.H> //onewire.c float getT(); //sys.c extern unsigned char UI; extern bit touch_mode; extern float jiaozhun; extern float canshu; extern float temper; void init74hc138(unsigned…...

编程日记 2025/8/20 8:11:34

ES：geoip_databases

如何查看 .geoip_databases 的内容在Elasticsearch中，.geoip_databases 是一个特殊的索引，用于存储GeoIP数据库文件。这些文件通常用于地理信息的丰富（GeoIP enrichment）。以下是如何查看和管理这些数据库文件的方法&#xff1a…...

编程日记 2025/8/18 0:54:13

输入格式:

输出格式:

输入样例:

输出样例:

相关文章：