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

代码随想录算法训练营Day56|所有可达路径、797.所有可能的路径

所有可达路径

98. 所有可达路径 (kamacoder.com)

深度优先搜索,和之前的回溯题类似。

#include <iostream>
#include <vector> 
using namespace std;// 定义一个二维向量来存储所有可能的路径
vector<vector<int>> paths;
// 定义一个向量来存储当前路径
vector<int> path;// 定义深度优先搜索函数
void dfs(const vector<vector<int>>& graph, int x, int n) {// 如果到达节点n,将当前路径添加到所有路径中if (x == n) {paths.push_back(path);return;}// 遍历所有可能的下一个节点for (int i = 1; i <= n; i++) {// 如果节点x和节点i之间有边(即连通)if (graph[x][i] == 1) {// 将节点i添加到当前路径path.push_back(i);// 递归地继续搜索从节点i开始的路径dfs(graph, i, n);// 回溯,移除节点i,尝试其他可能的路径path.pop_back();}}
}int main() {int N, M; // N表示节点数量,M表示边的数量cin >> N >> M; // 输入节点数量和边的数量// 创建一个(N+1) x (N+1)的二维向量,初始化所有值为0vector<vector<int>> graph(N + 1, vector<int>(N + 1, 0));int s, t;while (M--) { // 循环M次,输入每条边的两个节点cin >> s >> t;graph[s][t] = 1; // 表示节点s和节点t之间有边,即连通}// 从节点1开始搜索,将节点1添加到当前路径path.push_back(1);dfs(graph, 1, N); // 调用DFS函数搜索所有路径// 如果没有找到路径,输出-1if (paths.size() == 0)cout << -1 << endl;// 输出所有找到的路径for (auto x : paths) {for (int i = 0; i < x.size() - 1; i++) {cout << x[i] << " ";}cout << x[x.size() - 1] << endl;}
}

在构建图是,读入所有边,时间复杂度为O(M),在DFS是,最坏情况需要访问图中的每个节点和每天便,DFS的时间复杂度为O(N+M)。总的时间复杂度为O(N+M)。

空间复杂度,用邻接矩阵来存储graph信息需要(N+1)^2(从0到N+1的矩阵),paths在图全连接的情况下,可能要存储2^(N-1)条路(1-N),path为O(N),空间复杂度为O(2^(N-1))。

邻接链表参考

代码随想录 (programmercarl.com)

邻接数组也可以自己写写看。

所有可能的路径

797. 所有可能的路径 - 力扣(LeetCode)

上题的核心代码,代码如下,分析基本和上题相同。

class Solution {
public:// 定义一个向量来存储当前路径vector<int> path;// 定义一个二维向量来存储所有可能的路径vector<vector<int>> paths;// 定义深度优先搜索函数void dfs(const vector<vector<int>>& graph, int x, int n) {// 如果到达目标节点n,将当前路径添加到所有路径中if (x == n) {paths.push_back(path);return;}// 遍历当前节点的所有相邻节点for (int i = 0; i < graph[x].size(); i++) {// 将相邻节点添加到当前路径path.push_back(graph[x][i]);// 递归地继续搜索从相邻节点开始的路径dfs(graph, graph[x][i], n);// 回溯,移除刚刚添加的节点,以便尝试其他路径path.pop_back();}}vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {// 目标节点是图的最后一个节点 graph.size() - 1int n = graph.size() - 1;// 从源节点0开始,将源节点添加到当前路径path.push_back(0);// 调用DFS函数搜索所有路径dfs(graph, 0, n);// 返回找到的所有路径return paths;}
};

相关文章:

代码随想录算法训练营Day56|所有可达路径、797.所有可能的路径

所有可达路径 98. 所有可达路径 (kamacoder.com) 深度优先搜索&#xff0c;和之前的回溯题类似。 #include <iostream> #include <vector> using namespace std;// 定义一个二维向量来存储所有可能的路径 vector<vector<int>> paths; // 定义一个向…...

DNF手游鬼剑士攻略:全面解析流光星陨刀的获取与升级!云手机强力辅助!

《地下城与勇士》&#xff08;DNF&#xff09;手游是一款广受欢迎的多人在线角色扮演游戏&#xff0c;其中鬼剑士作为一个经典职业&#xff0c;因其强大的输出能力和炫酷的技能特效&#xff0c;吸引了众多玩家的青睐。在这篇攻略中&#xff0c;我们将详细介绍鬼剑士的一把重要武…...

npm创建一个空的vue3项目的方法或者pnpm创建vue3项目

1、前提我们已经安装了npm&#xff0c;或者pnpm 2、我们用npm来创建vue3项目 快速上手 | Vue.js 官网地址 这里我安装是的 node v18.20.3 以下是安装过程 &#xff1a; npm create vuelatest 根据自己的需要进行创建即可。 3、我们用pnpm来创建vite vue3项目 pnpm create …...

LSH算法:高效相似性搜索的原理与Python实现I

局部敏感哈希&#xff08;LSH&#xff09;技术是快速近似最近邻&#xff08;ANN&#xff09;搜索中的一个关键方法&#xff0c;广泛应用于实现高效且准确的相似性搜索。这项技术对于许多全球知名的大型科技公司来说是不可或缺的&#xff0c;包括谷歌、Netflix、亚马逊、Spotify…...

cesium 添加 Echarts图层(人口迁徒图)

cesium 添加 Echarts 人口迁徒图(下面附有源码) 1、实现思路 1、在scene上面新增一个canvas画布 2、通坐标转换,将经纬度坐标转为屏幕坐标来实现 3、将ecarts 中每个series数组中元素都加 coordinateSystem: ‘cesiumEcharts’ 2、示例代码 <!DOCTYPE html> <ht…...

Windows下快速安装Open3D-0.18.0(python版本)详细教程

目录 一、Open3D简介 1.1主要用途 1.2应用领域 二、安装Open3D 2.1 激活环境 2.2 安装open3d 2.3测试安装是否成功 三、测试代码 3.1 代码 3.2 显示效果 一、Open3D简介 Open3D 是一个强大的开源库&#xff0c;专门用于处理和可视化3D数据&#xff0c;如点云、网格和…...

无法下载 https://mirrors./ubuntu/dists/bionic/main/binary-arm64/Packages

ubuntu系统执行sudo apt update命令的时候&#xff0c;遇到如下问题&#xff1a; 忽略:82 https://mirrors.tuna.tsinghua.edu.cn/ubuntu bionic-backports/universe arm64 Packages 错误:81 https://mirrors.tuna.tsinghua.edu.cn/ubuntu bionic-backports/main arm64 Packa…...

最新CRMEB商城多商户java版源码v1.6版本+前端uniapp

CRMEB 开源商城系统Java版&#xff0c;基于JavaVueUni-app开发&#xff0c;在微信公众号、小程序、H5移动端都能使用&#xff0c;代码全开源无加密&#xff0c;独立部署&#xff0c;二开很方便&#xff0c;还支持免费商用&#xff0c;能满足企业新零售、分销推广、拼团、砍价、…...

【开发环境】MacBook M2安装git并拉取gitlab项目,解决gitlab出现Access Token使用无效的方法

文章目录 安装Homebrew安装git打开IDEA配置git打开IDEA拉取项目 安装Homebrew /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"在iTerm等命令行工具打开后&#xff0c;输入上面的命令 之后根据中文提示完成Homebrew的下载…...

Flask-Session使用Redis

Flask-Session使用Redis 一、介绍 在Flask中&#xff0c;session数据默认是以加密的cookie形式存储在用户的浏览器中的。但是&#xff0c;真正的session数据应该存储在服务器端。Django框架会将session数据存储在数据库的djangosession表中&#xff0c;而Flask则可以通过第三…...

Redis缓存管理机制

在当今快节奏的数字世界中&#xff0c;性能优化对于提供无缝的用户体验至关重要。缓存在提高应用程序性能方面发挥着至关重要的作用&#xff0c;它通过将经常使用或处理的数据存储在临时高速存储中来减少数据库负载并缩短响应时间&#xff0c;从而减少系统的延迟。Redis 是一种…...

初学嵌入式是弄linux还是单片机?

在开始前刚好我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「单片机的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“666”之后私信回复“666”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01;1、先入门了51先学了89c52…...

【基础算法总结】分治—快排

分治—快排 1.分治2.颜色分类3.排序数组4.数组中的第K个最大元素5.库存管理 III 点赞&#x1f44d;&#x1f44d;收藏&#x1f31f;&#x1f31f;关注&#x1f496;&#x1f496; 你的支持是对我最大的鼓励&#xff0c;我们一起努力吧!&#x1f603;&#x1f603; 1.分治 分治…...

[C++]——同步异步日志系统(1)

同步异步日志系统 一、项⽬介绍二、开发环境三、核心技术四、环境搭建五、日志系统介绍5.1 为什么需要日志系统5.2 日志系统技术实现5.2.1 同步写日志5.2.2 异步写日志 日志系统&#xff1a; 日志&#xff1a;程序在运行过程中&#xff0c;用来记录程序运行状态信息。 作用&…...

python 第6册 辅助excel 002 批量创建非空白的 Excel 文件

---用教授的方式学习 此案例主要通过使用 while 循环以及 openpyxl. load_workbook()方法和 Workbook 的 save()方法&#xff0c;从而实现在当前目录中根据已经存在的Excel 文件批量创建多个非空白的Excel 文件。当运行此案例的Python 代码&#xff08;A002.py 文件&#xff0…...

力扣61. 旋转链表(java)

思路&#xff1a;用快慢指针找到最后链表k个需要移动的节点&#xff0c;然后中间断开节点&#xff0c;原尾节点连接原头节点&#xff0c;返回新的节点即可&#xff1b; 但因为k可能比节点数大&#xff0c;所以需要先统计节点个数&#xff0c;再取模&#xff0c;看看k到底需要移…...

智慧园区综合平台解决方案PPT(75页)

## 智慧园区的理解 ### 从园区1.0到园区4.0的演进 1. 园区1.0&#xff1a;以土地经营为主&#xff0c;成本驱动&#xff0c;提供基本服务。 2. 园区2.0&#xff1a;服务驱动&#xff0c;关注企业成长&#xff0c;提供增值服务。 3. 园区3.0&#xff1a;智慧型园区&#xff…...

Python只读取Excel文件的一部分数据,比如特定范围的行和列?

如何只读取Excel文件的一部分数据&#xff0c;比如特定范围的行和列&#xff1f; 在Python中&#xff0c;如果你只想读取Excel文件的特定范围&#xff0c;可以使用以下方法&#xff1a; pandas: Pandas是一个强大的数据处理库&#xff0c;它有一个内置函数read_excel()用于读…...

快速入门FreeRTOS心得(正点原子学习版)

对于FreeROTS&#xff0c;我第一反应想到的就是通信里的TDM&#xff08;时分多址&#xff09;。不同任务给予分配不同的时间间隔&#xff0c;也就是任务之间在每个timeslot都在来回切换。 这里有重要的一点&#xff0c;就是中断要短小&#xff0c;优先级是自高到底进行打断。 …...

【博主推荐】HTML5实现简洁好看的个人简历网页模板源码

文章目录 1.设计来源1.1 主界面1.2 关于我界面1.3 工作经验界面1.4 学习教育界面1.5 个人技能界面1.6 专业特长界面1.7 朋友评价界面1.8 获奖情况界面1.9 联系我界面 2.效果和源码2.1 动态效果2.2 源代码 源码下载万套模板&#xff0c;程序开发&#xff0c;在线开发&#xff0c…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...