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

代码随想录算法【Day50】

Day50

图的基础知识

图的种类:有向图,无向图,带权值的图

有多少条边连接这个节点就是几度

出度:从该节点指到别的节点的边

入度:与“出度”相反

连通性 一般在无向图中研究

连通图:任何一个节点都可以到达其它的所有节点

强连通图:有向图中的连通性

连通分量:极大连通子图。例如一个图里面有两个子图,其中的某子图中的任何一个节点都可以到达其它的所有节点,那么这个子图就是一个连通分量。

强连通分量:有向图里,概念和上面类似。

图的构造

朴素存储:定义一个n*2的二维数组,存放节点的连接情况。缺点:不好查找。

邻接矩阵:定义一个n*n的二维数组,例如节点1指向节点2,并且权值为6,则数组grad[1][2]存放权值6。缺点:浪费空间。

邻接表:将数组和链表相连。缺点:节点越多,空间越大。

边很多适合用邻接矩阵,节点很多适合用邻接表

图的遍历

DFS

BFS

二叉树里的递归遍历(前序遍历、中序遍历、后序遍历)也就是深度优先搜索,二叉树里的层序遍历也就是广度优先搜索

深搜理论基础

深搜代码三部曲:

1.确定函数dfs()和参数

2.确立终止条件

3.处理节点

vector<vector<int>> result; //结果集
vector<int> path; //记录单条路径,后面放入结果集
void dfs(图,目前搜索的节点){if(终止条件){存放结果return;}for(选择本节点所连接的节点){处理结点dfs(图,选择的节点)回溯,撤销处理结果}
}
98. 所有可达路径
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径
​
void dfs (const vector<vector<int>>& graph, int x, int n) {// 当前遍历的节点x 到达节点n if (x == n) { // 找到符合条件的一条路径result.push_back(path);return;}for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点if (graph[x][i] == 1) { // 找到 x链接的节点path.push_back(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.pop_back(); // 回溯,撤销本节点}}
}
​
int main() {int n, m, s, t;cin >> n >> m;
​// 节点编号从1到n,所以申请 n+1 这么大的数组vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));
​while (m--) {cin >> s >> t;// 使用邻接矩阵 表示无线图,1 表示 s 与 t 是相连的graph[s][t] = 1;}
​path.push_back(1); // 无论什么路径已经是从0节点出发dfs(graph, 1, n); // 开始遍历
​// 输出结果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl;}
}

相关文章:

代码随想录算法【Day50】

Day50 图的基础知识 图的种类&#xff1a;有向图&#xff0c;无向图&#xff0c;带权值的图 度 有多少条边连接这个节点就是几度 出度&#xff1a;从该节点指到别的节点的边 入度&#xff1a;与“出度”相反 连通性 一般在无向图中研究 连通图&#xff1a;任何一个节点都…...

禁止WPS强制打开PDF文件

原文网址&#xff1a;禁止WPS强制打开PDF文件_IT利刃出鞘的博客-CSDN博客 简介 本文介绍如何避免WPS强制打开PDF文件。 方法 1.删除注册表里.pdf的WPS绑定 WinR&#xff0c;输入&#xff1a;regedit&#xff0c;回车。找到&#xff1a;HKEY_CLASSES_ROOT\.pdf删除KWPS.PDF…...

DeepSeek R1生成图片总结2(虽然本身是不能直接生成图片,但是可以想办法利用别的工具一起实现)

DeepSeek官网 目前阶段&#xff0c;DeepSeek R1是不能直接生成图片的&#xff0c;但可以通过优化文本后转换为SVG或HTML代码&#xff0c;再保存为图片。另外&#xff0c;Janus-Pro是DeepSeek的多模态模型&#xff0c;支持文生图&#xff0c;但需要本地部署或者使用第三方工具。…...

深入解析NoSQL数据库:从文档存储到图数据库的全场景实践

title: 深入解析NoSQL数据库:从文档存储到图数据库的全场景实践 date: 2025/2/19 updated: 2025/2/19 author: cmdragon excerpt: 通过电商、社交网络、物联网等12个行业场景,结合MongoDB聚合管道、Redis Stream实时处理、Cassandra SSTable存储引擎、Neo4j路径遍历算法等42…...

大模型WebUI:Gradio全解11——使用transformers.agents构建Gradio UI(3)

大模型WebUI&#xff1a;Gradio全解11——使用transformers.agents构建Gradio UI&#xff08;3&#xff09; 前言本篇摘要11. 使用transformers.agents构建Gradio UI11.3 创建和使用工具Tools11.3.1 默认工具箱与load_tool11.3.2 创建新工具11.3.3 管理代理的工具箱toolbox11.3…...

Mybatis-Plus的使用

1. MyBatis-Plus介绍 MyBatis-Plus(简称 MP)是⼀个MyBatis的增强⼯具,在MyBatis的基础上只做增强不做改变,为简化开 发.提⾼效率⽽⽣ 特性: • 润物⽆声:只做增强不做改变&#xff0c;引⼊它不会对现有⼯程产⽣影响&#xff0c;如丝般顺滑. • 效率⾄上:只需简单配置&#…...

基于YOLO11深度学习的心脏超声图像间隔壁检测分割与分析系统【python源码+Pyqt5界面+数据集+训练代码】深度学习实战、目标分割、人工智能

《------往期经典推荐------》 一、AI应用软件开发实战专栏【链接】 项目名称项目名称1.【人脸识别与管理系统开发】2.【车牌识别与自动收费管理系统开发】3.【手势识别系统开发】4.【人脸面部活体检测系统开发】5.【图片风格快速迁移软件开发】6.【人脸表表情识别系统】7.【…...

什么是神经网络?

0 前言 神经网络是一种人工智能方法&#xff0c;用于教计算机以受人脑启发的方式处理数据。这是一种机器学习过程&#xff0c;称为深度学习&#xff0c;它使用类似于人脑的分层结构中的互连节点或神经元。它可以创建自适应系统&#xff0c;计算机使用该系统来从错误中进行学习…...

【第12章:深度学习与伦理、隐私—12.1 AI伦理原则与偏见检测的方法与实践】

凌晨三点,某法院的AI量刑系统突然将一桩盗窃案的刑期预测从6个月改为3年——只因被告人的居住地邮编关联到某个少数族裔聚居区。这场静默的算法叛乱,揭开了AI伦理问题的冰山一角。 一、AI伦理的五大天条 1.1 公平性原则:算法没有"完美中立" ![不同算法在COMPAS…...

运用先进的智能算法和优化模型,进行科学合理调度的智慧园区开源了

智慧园区场景视频监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒&#xff0c;省去繁琐重复的适配流程&#xff0c;实现芯片、算法、应用的全流程组合&#xff0c;从而大大减少企业级应用约95%的开发成本。充分利用现有…...

Redis过期机制

const (cacheDuration 24 * time.Hour )func SetToCache(rdb *redis.Client, key string, data []byte) error {return rdb.Set(rdb.Context(), key, data, cacheDuration).Err() }以上函数中的rdb.Set(rdb.Context(), key, data, cacheDuration).Err()中的 cacheDuration一旦…...

Android ListPreference使用

Android ListPreference使用 参考 添加链接描述 导入 androidx.preference.ListPreferenceListPreference是Android中的一个Preference子类,用于显示一个可选择的列表,并且可以保存用户所选择的值。它继承自DialogPreference,可以在用户点击时弹出一个对话框,显示可选择的…...

10分钟上手DeepSeek开发:SpringBoot + Vue2快速构建AI对话系统

作者&#xff1a;后端小肥肠 目录 1. 前言 为什么选择DeepSeek&#xff1f; 本文技术栈 2. 环境准备 2.1. 后端项目初始化 2.2. 前端项目初始化 3. 后端服务开发 3.1. 配置文件 3.2. 核心服务实现 4. 前端服务开发 4.1. 聊天组件ChatWindow.vue开发 5. 效果展示及源…...

瑞芯微RV1126部署YOLOv8全流程:环境搭建、pt-onnx-rknn模型转换、C++推理代码、错误解决、优化、交叉编译第三方库

目录 1 环境搭建 2 交叉编译opencv 3 模型训练 4 模型转换 4.1 pt模型转onnx模型 4.2 onnx模型转rknn模型 4.2.1 安装rknn-toolkit 4.2.2 onn转成rknn模型 5 升级npu驱动 6 C++推理源码demo 6.1 原版demo 6.2 增加opencv读取图片的代码 7 交叉编译x264 ffmepg和op…...

泰山派RK3566移植QT,动鼠标时出现屏幕闪烁

总结&#xff1a; 交叉编译到 泰山派rk3566跑调海康摄像头的qt应用程序失败了。 X11无效窗口。 移植QT注意 屏幕分辨率不要改。改了执行QT的时候&#xff0c;framebuffer识别不出设备。 命令行安装QT-Creator sudo install 类似的指令安装Qt-Creator时&#xff0c;可能找不到编…...

一周学会Flask3 Python Web开发-post请求与参数获取

锋哥原创的Flask3 Python Web开发 Flask3视频教程&#xff1a; 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili app.route 装饰器默认只支持get请求。假如我们要让绑定的视图函数支持其他请求方式&#xff0c;我们可以在methods属性里配置…...

Vue 3 中可读可写的计算属性(Computed Properties)的使用场景

在 Vue 3 中&#xff0c;计算属性&#xff08;Computed Properties&#xff09;是一种基于响应式依赖进行缓存的属性。它们通常用于处理复杂的逻辑&#xff0c;并且只有当依赖的响应式数据发生变化时&#xff0c;才会重新计算。计算属性非常适合用于处理模板中的复杂表达式&…...

EXCEL解决IF函数“您已为此函数输入太多个参数”的报错

IF函数的基本结构是IF(条件, 值为真时的结果, 值为假时的结果)&#xff0c;所以标准的IF函数最多只能有三个参数。当用户输入的参数超过三个时&#xff0c;Excel就会报这个错误。比如多个IF语句叠加&#xff0c;但可能在嵌套的过程中没有正确关闭每个IF函数的括号&#xff0c;导…...

Redis7——基础篇(二)

前言&#xff1a;此篇文章系本人学习过程中记录下来的笔记&#xff0c;里面难免会有不少欠缺的地方&#xff0c;诚心期待大家多多给予指教。 基础篇&#xff1a; Redis&#xff08;一&#xff09; 接上期内容&#xff1a;上期完成了Redis环境的搭建。下面开始学习Redis常用命令…...

vue3 ref和reactive的区别

在 Vue 3 中&#xff0c;ref 和 reactive 是两种用于创建响应式数据的 API&#xff0c;但它们的使用场景和实现方式有一些区别。用大白话来说&#xff0c;它们的区别可以这样理解&#xff1a; 1. ref&#xff1a;适合处理简单数据 是什么&#xff1a;ref 是用来包装一个基本类…...

Elasticsearch7.1.1 配置密码和SSL证书

生成SSL证书 ./elasticsearch-certutil ca -out config/certs/elastic-certificates.p12 -pass 我这里没有设置ssl证书密码&#xff0c;如果需要设置密码&#xff0c;需要再配置给elasticsearch 在之前的步骤中&#xff0c;如果我们对elastic-certificates.p12 文件配置了密码…...

初识Redis

1.什么是Redis Redis是一种基于键值对&#xff08;key-value&#xff09;的NoSQL数据库。与很多键值对数据库不同的是&#xff0c;Redis中的value可以由String&#xff08;字符串&#xff09;&#xff0c;hash&#xff08;哈希&#xff09;&#xff0c;list&#xff08;列表&a…...

Python Selenium自动化操作详解:从入门到实战

Python Selenium自动化操作详解&#xff1a;从入门到实战 一、Selenium简介 Selenium是一个用于Web应用程序自动化测试的工具&#xff0c;支持多种浏览器和编程语言。结合Python使用&#xff0c;可以实现&#xff1a; 自动化表单提交动态网页数据抓取功能测试网页交互模拟 二…...

第四天面试题

文章目录 1.什么叫 Java 的内存泄露与内存溢出&#xff1f;**1. 内存泄露&#xff08;Memory Leak&#xff09;****内存泄露的常见原因&#xff1a;****如何避免内存泄露&#xff1a;** **2. 内存溢出&#xff08;Out Of Memory, OOM&#xff09;****内存溢出的常见原因&#x…...

[论文阅读] SeeSR: Towards Semantics-Aware Real-World Image Super-Resolution

文章目录 一、前言二、主要贡献三、Introduction四、Methodology4.1 Motivation &#xff1a;4.2Framework Overview.** 一、前言 通信作者是香港理工大学 & OPPO研究所的张磊教授&#xff0c;也是图像超分ISR的一个大牛了。 论文如下 SeeSR: Towards Semantics-Aware Rea…...

面试题之箭头函数和普通函数有什么区别?

箭头函数&#xff08;Arrow Function&#xff09;和普通函数&#xff08;Regular Function&#xff09;是 JavaScript 中两种不同的函数定义方式&#xff0c;它们在语法、上下文&#xff08;this&#xff09;、原型链等方面存在显著区别。以下是它们的主要区别&#xff1a; 1. …...

jQuery AJAX 方法详解

jQuery AJAX 方法详解 引言 随着互联网技术的不断发展,前端开发领域的技术也在不断更新迭代。jQuery 作为一种广泛使用的前端JavaScript库,极大地简化了DOM操作和事件处理。在众多jQuery功能中,AJAX(Asynchronous JavaScript and XML)方法尤为突出,它允许我们在不重新加…...

深度集成DeepSeek大模型:WebSocket流式聊天实现

目录 5分钟快速接入DeepSeek大模型&#xff1a;WebSocket实时聊天指南创建应用开发后端代码 (Python/Node.js)结语 5分钟快速接入DeepSeek大模型&#xff1a;WebSocket实时聊天指南 创建应用 访问DeepSeek官网 前往 DeepSeek官网。如果还没有账号&#xff0c;需要先注册一个。…...

千峰React:组件使用(1)

事件 添加点击事件 function App() {const handClick () > {console.log(123)}return (<><button onClick{handClick}>点击</button></>) } export default App在react里也可以添加事件对象e 合成e 这个e和js里的e不太一样&#xff0c;是合成的…...

ram的使用——初始化很重要

背景 ram是非常常用的ip&#xff0c;前人的经验告诉我们&#xff0c;如果不对ram进行初始化直接读写&#xff0c;不定态在实际上板时会出现不可预知的问题。 我们需要对ram进行初始化写0操作&#xff0c;代码如下。需要注意&#xff0c;复位释放时立马写入可能存在复位抖动的…...

JVM深入理解

目录 JVM介绍&#xff1a; 解释&#xff1a; 特点&#xff1a; 整体构成&#xff1a; 执行过程&#xff1a; 运行时数据区&#xff1a; Java堆剖析&#xff1a; 堆内存区域划分 为什么要分代呢&#xff1f; 内存分配&#xff1a; 新生区与老年区配置比例&#xff1a…...

DeepSeek 开放平台无法充值 改用其他平台API调用DeepSeek-chat模型方法

近几天DeepSeek开放平台无法充值目前已经关闭状态&#xff0c;大家都是忙着接入DeepSeek模型 &#xff0c;很多人想使用DeepSeek怎么办&#xff1f; 当然还有改用其他平台API调用方法&#xff0c;本文以本站的提供chatgpt系统为例&#xff0c;如何修改DeepSeek-chat模型API接口…...

ImportError: cannot import name ‘FixtureDef‘ from ‘pytest‘

错误信息表明 pytest 在尝试导入 FixtureDef 时出现了问题。通常是由于 pytest 版本不兼容 或 插件版本冲突 引起的。以下是详细的排查步骤和解决方案&#xff1a; 1. 检查 pytest 版本 首先&#xff0c;确认当前安装的 pytest 版本。某些插件可能需要特定版本的 pytest 才能…...

懒人精灵本地离线卡密验证系统教程(不联网、安全稳定、省钱、永久免费、无任何限制)

1.合集懒人精灵本地离线卡密验证系统教程(不联网、安全稳定、省钱、永久免费、无任何限制)&#xff1a;https://www.bilibili.com/video/BV1M6rdYEEog/ 备注&#xff1a; 1.本地离线卡密采用最安全的非对称加解密技术&#xff0c;设备id采用最安全多重混合加密不可逆技术生成&…...

Rust编程语言入门教程 (六)变量与可变性

Rust 系列 &#x1f380;Rust编程语言入门教程&#xff08;一&#xff09;安装Rust&#x1f6aa; &#x1f380;Rust编程语言入门教程&#xff08;二&#xff09;hello_world&#x1f6aa; &#x1f380;Rust编程语言入门教程&#xff08;三&#xff09; Hello Cargo&#x1f…...

ArcGis和Super Map

1.ArcGIS ArcGIS 是美国环境系统研究所&#xff08;ESRI&#xff09;开发的一系列地理信息系统&#xff08;GIS&#xff09;软件产品的总称&#xff0c;它提供了一套全面的工具和服务&#xff0c;可用于采集、存储、分析、管理和展示地理数据&#xff0c;在众多领域都有广泛的…...

POI优化Excel录入

57000单词原始录入时间258S 核心代码: List<Word> wordBookList ExcelUtil.getReader(file.getInputStream()).readAll(Word.class);if (!CollectionUtil.isEmpty(wordBookList)) {for (Word word : wordBookList) {//逐条向数据库中插入单词wordMapper.insert(word);}…...

Zookeeper和Kafka的依赖关系

Zookeeper 和 Kafka 是紧密相关的,它们在功能上相互协作,共同为分布式系统提供支持,以下是它们的关系具体介绍: Kafka 依赖 Zookeeper 进行元数据管理 主题信息存储:Kafka 中的主题(Topic)相关信息,如主题的名称、分区数量、副本分布等都存储在 Zookeeper 中。当 Kafk…...

驱动开发、移植

一、任务明确&#xff1a;把创龙MX8的驱动 按照我们的要求 然后移植到 我们的板子 1.Linux系统启动卡制作&#xff0c; sd卡 先按照 《用户手册—3-2-Linux系统启动卡制作及系统固化》 把创龙的Linux系统刷进去。 2. 把TLIMX8-EVM的板子过一遍 把刚刚烧好系统的sd卡插入 创…...

RT-Thread+STM32L475VET6实现红外遥控实验

文章目录 前言一、板载资源介绍二、具体步骤1. 确定红外接收头引脚编号2. 下载infrared软件包3. 配置infrared软件包4. 打开STM32CubeMX进行相关配置4.1 使用外部高速时钟&#xff0c;并修改时钟树4.2 打开定时器16(定时器根据自己需求调整)4.3 打开串口4.4 生成工程 5. 打开HW…...

分布式大语言模型服务引擎vLLM论文解读

论文地址&#xff1a;Efficient Memory Management for Large Language Model Serving with PagedAttention 摘要 大语言模型&#xff08;LLMs&#xff09;的高吞吐量服务需要一次对足够多的请求进行批处理。然而&#xff0c;现有系统面临困境&#xff0c;因为每个请求的键值…...

Bio-ORACLE数据分享[decade 2010-2020] [Surface layers]

Bio-ORACLE数据分享[decade 2010-2020] [Surface layers] 文章目录 Bio-ORACLE数据分享[decade 2010-2020] [Surface layers]前言一、文件分享&#xff08;主要&#xff09;二、相关代码&#xff08;选看&#xff09;总结 Bio-ORACLE数据分享[decade 2010-2020] [Surface layer…...

MySQL六大日志的功能介绍。

前言 首先&#xff0c;MySQL的日志应该包括二进制日志&#xff08;Binary Log&#xff09;、错误日志&#xff08;Error Log&#xff09;、查询日志&#xff08;General Query Log&#xff09;、慢查询日志&#xff08;Slow Query Log&#xff09;、重做日志&#xff08;Redo …...

ChatGPT客户端无法在微软应用商店下载的解决方法

最近网页端的GPT4o只会用how can I assist you 回复了&#xff0c;查了一下发现是类似IP封锁/模型降级等等问题&#xff0c;总之解决方法就是下载客户端。客户端需要通过微软应用商店下载&#xff0c;但是下载时总会出现如下情况&#xff1a; 1.区域和语言没有设置为美国/英语导…...

数仓搭建(hive):DWS层(服务数据层)

DWS层示例: 搭建日主题宽表 需求 维度 步骤 在hive中建数据库dws >>建表 CREATE DATABASE if NOT EXISTS DWS; 建表sql CREATE TABLE yp_dws.dws_sale_daycount( --维度 city_id string COMMENT 城市id, city_name string COMMENT 城市name, trade_area_id string COMME…...

Ollama+DeepSeek+Open-WebUi

环境准备 Docker Ollama Open-WebUi Ollama 下载地址&#xff1a;Ollama docker安装ollama docker run -d \ -v /data/ollama/data:/root/.ollama \ -p 11434:11434 \ --name ollama ollama/ollama 下载模型 Ollama模型仓库 # 示例&#xff1a;安装deepseek-r1:7b doc…...

【笔记】LLM|Ubuntu22服务器极简本地部署DeepSeek+联网使用方式

2025/02/18说明&#xff1a;2月18日~2月20日是2024年度博客之星投票时间&#xff0c;走过路过可以帮忙点点投票吗&#xff1f;我想要前一百的实体证书&#xff0c;经过我严密的计算只要再拿到60票就稳了。一人可能会有多票&#xff0c;Thanks♪(&#xff65;ω&#xff65;)&am…...

FreeSwitch中mod_dptools和mod_easyroute两个模块及应用场景

FreeSWITCH 中的 mod_dptools 和 mod_easyroute 是两个功能不同的模块&#xff0c;分别服务于呼叫控制和动态路由场景。以下是详细介绍&#xff1a; mod_dptools 功能概述 mod_dptools&#xff08;Dialplan Tools&#xff09;是 FreeSWITCH 最核心的模块之一&#xff0c;提供了…...

【Java】泛型与集合篇 —— Set 接口

目录 Set 接口及实现类HashSet 类特点内部实现构造方法LinkedHashSet 类基本概念特点构造方法常用方法适用场景用 Set 对象实现集合运算TreeSet 类特性构造方法常用方法注意事项对象顺序自然排序定制排序注意事项Set 接口及实现类 HashSet 类 HashSet 是 Java 集合框架中 Set…...

DeepSeek 助力 Vue 开发:打造丝滑的右键菜单(RightClickMenu)

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 Deep…...