代码随想录算法训练营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)的二维向量,初始化所有值为0
    vector<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函数搜索所有路径
    
    // 如果没有找到路径,输出-1
    if (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() - 1
        int n = graph.size() - 1;
        // 从源节点0开始,将源节点添加到当前路径
        path.push_back(0);
        // 调用DFS函数搜索所有路径
        dfs(graph, 0, n);
        // 返回找到的所有路径
        return paths;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/765081.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

分文件编译(简单学生系统)

定义学生基本信息 ①输出所有学生信息 ②删除某个学生后&#xff0c;输出所有学生信息 ③修改某个学生信息后&#xff0c;输出所有学生信息 ④查找某个学生的信息 main.c #include"k11*.h" int main(int argc, const char *argv[]) {struct student p[4]{{"…

注意!年龄越大,社交圈子越窄?其实这是老人的理性选择!数学家告诉你:何时该跳槽,何时该坚守!你必须知道的三个智慧:让你的人生更加精彩!

我们到底应该在什么情况下探索新事物&#xff0c;什么情况下专注于已有的东西呢&#xff1f;本质上来说&#xff0c;这个问题就是在询问&#xff0c;你究竟应该耗费精力去探索新的信息&#xff0c;还是专注从既有的信息中获取收获&#xff1f; 有人采访了临终的老人&#xff0c…

51单片机外部中断(按键识别)

欢迎入群共同学习交流 时间记录&#xff1a;2024/7/2 一、电路原理图 51单片机包含INT0、INT1两个外部中断接口 二、知识点介绍 1.中断寄存器位介绍 &#xff08;1&#xff09;TCON定时控制寄存器&#xff0c;位0&#xff08;IT0&#xff09;中断INT0请求信号选择位&#x…

win11电源设置

把钩子去掉以后 win11的电脑关机才有用 否则&#xff0c;关机了&#xff0c;电脑也实际上一直在运行

边缘计算网关在现代工业企业中的作用-天拓四方

随着工业4.0时代的到来&#xff0c;数字化转型已经成为工业企业发展的必然趋势。在这一过程中&#xff0c;边缘计算网关以其独特的优势&#xff0c;正逐渐成为工业企业实现智能化、高效化运营的关键技术。 边缘计算网关是一种部署在网络边缘的设备&#xff0c;它集成了计算、存…

nginx 只有图片等静态资源时 监听80端口 会404 NOT FOUND

解决方法 删除 /var/nginx/sites-enabled 原因&#xff1a;当nginx没有设置首页路径index时&#xff0c;sites-enabled目录中配置的优先级会高于nginx.conf 导致404 NOT FOUND sites-enabled文件中的default会将80端口索引至默认值&#xff1a;/var/www/html目录下&#xff…

数据库。

数据库安全性 论述题5’ 编程题10’ sql语言实现权限控制 一、概述 1、不安全因素 &#xff08;1&#xff09;⾮授权对数据库的恶意存取和破坏 &#xff08;2&#xff09;数据库中重要的数据泄露 &#xff08;3&#xff09;安全环境的脆弱性 2、⾃主存取控制⽅法 gr…

【Qt知识】Geometry属性

一、走进Geometry的世界 Geometry属性是Qt框架中用于处理和操作几何形状的一系列类的集合。它包括了QPoint、QPointF、QSize、QSizeF、QRect和QRectF等。这些类分别代表点、大小、矩形等基本几何概念&#xff0c;它们的存在让图形界面的创建变得既简单又直观。 位置和尺寸。 其…

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

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

武汉星起航:成功挂牌上股交,引领跨境电商行业进入全新发展阶段

2023年10月30日&#xff0c;武汉星起航电子商务有限公司在上海股权托管交易中心成功挂牌展示&#xff0c;这一里程碑式的事件标志着武汉星起航正式登陆资本市场&#xff0c;开启了公司发展的新篇章。作为亚马逊跨境电商领域的领军企业之一&#xff0c;武汉星起航此次挂牌不仅是…

时序约束(二): input delay约束和output delay约束

一、input delay约束 在千兆以太网数据收发项目中&#xff0c;RGMII的数据输入方式为DDR&#xff0c;源同步输入方式&#xff0c;可以用之前提到的分析模型进行约束。 在时序约束原理中我们提到&#xff0c;input delay约束的就是发射沿lunch到数据有效的延时&#xff0c;根据…

comfyui定制

&#x1f31f; comfyui定制AI人工智能公司— 触站AI&#xff0c;绘制智能图像新纪元 &#x1f3a8; &#x1f680;AI绘画&#xff0c;触站AI引领创新潮流 &#x1f680;深圳&#xff0c;这座创新之城&#xff0c;迎来了触站AI&#xff0c;一家专注于企业AI图像领域的技术解决方…

无法下载 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…

comfyui定制外包

&#x1f308; 最强AI绘画comfyui模型训练、定制服务公司出炉 —— 触站AI&#xff0c;引领设计智能新潮流 &#x1f680; &#x1f3a8; 触站AI&#xff0c;以AI绘画模型训练重塑设计边界 &#x1f3a8;在AI技术的浪潮中&#xff0c;触站AI以其前沿的AI绘画模型训练技术&…

已解决java.awt.geom.NoninvertibleTransformException:在Java2D中无法逆转的转换的正确解决方法,亲测有效!!!

已解决java.awt.geom.NoninvertibleTransformException&#xff1a;在Java2D中无法逆转的转换的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 目录 问题分析 出现问题的场景 报错原因 解决思路 解决方法 1. 检查缩放因子 修改后的缩放变换 …

申请一张含100个域名的证书-免费SSL证书

挑战一下&#xff0c;申请一张包含100个域名的证书 首先&#xff0c;我们访问来此加密网站&#xff0c;进入登录页面&#xff0c;输入我的账号密码。 登录后&#xff0c;咱们就可以开始申请证书&#xff0c;首先说一下&#xff0c;咱账号是SVIP哦&#xff0c;只有SVIP才可以申…

【如何使用RSA签名验签】python语言

文章目录 签名方法异步同步通知数据验签生活号响应数据验签同步响应数据验签 &#x1f308;你好呀&#xff01;我是 山顶风景独好 &#x1f388;欢迎踏入我的博客世界&#xff0c;能与您在此邂逅&#xff0c;真是缘分使然&#xff01;&#x1f60a; &#x1f338;愿您在此停留的…

通过MATLAB控制TI毫米波雷达的工作状态

前言 前一章博主介绍了MATLAB上位机软件“设计视图”的制作流程,这一章节博主将介绍如何基于这些组件结合MATLAB代码来发送CFG指令控制毫米波雷达的工作状态 串口配置 首先,在我们选择的端口号输入框和端口波特率设置框内是可以手动填入数值(字符)的,也可以在点击运行后…

Python的matplotlib简单操作及图像闪屏问题

1.显示一个sinx的图像 import matplotlib.pyplot as plt import numpy as np xnp.linspace(0,10,100)#生成0到10 之间 分成100份等间隔 ynp.sin(x) # # plt.plot(x,y)#放入x与y plt.title("ysin(x)")#给图像命名 plt.xlabel("x")#设置x位置的名字 plt.yl…

【CT】LeetCode手撕—19. 删除链表的倒数第 N 个结点

题目 原题连接&#xff1a;19. 删除链表的倒数第 N 个结点 1- 思路 模式识别&#xff1a;删除倒数第 n 个结点 ——> 定义 dummyHead 并用双指针实现删除逻辑 2- 实现 ⭐19. 删除链表的倒数第 N 个结点——题解思路 class Solution {public ListNode removeNthFromEnd(Li…