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

代码随想录算法训练营第六十四天 | 图论理论基础、深搜理论基础、广搜理论基础、98. 所有可达路径

图论理论基础

我写在了个人语雀笔记中

https://www.yuque.com/yuqueyonghu8mml9e/bmbl71/ex473q4y0ebs0l3r?singleDoc# 

深搜理论基础

https://www.yuque.com/yuqueyonghu8mml9e/bmbl71/zamfikz08c2haptn?singleDoc#

98. 所有可达路径

题目链接:98. 所有可达路径 

文字讲解:98. 所有可达路径 | 代码随想录 

解题思路

邻接矩阵

1.确认递归函数和参数

首先dfs函数中,一定要有一个图,其次是我们当前遍历的节点,为x

其次还需要一个n,来表示终点,当x==n时则表示达到了终点

最后就是需要保存单一路径的path,和结果result了

2.确定终止条件

当我们的x==n时,则我们找到了从出发点到结束点的路径

3.处理目前搜索节点的路径

首先我们是要找到x节点指向了哪些节点?

for(int i = 1 ; i<=n ; i++)
{if(graph[x][i]==1){//找到x指向的节点,就是节点i//此时我们要将x指向的节点加入到path中path.push_back(i);//进入下一层递归dfs(graph,i,n);//回溯的过程path.pop_back();   }
}

4.打印结果

// 输出结果
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; // 这里再打印倒数第一个,控制最后一个元素后面没有空格
}

完整代码: 

#include<bits/stdc++.h>
using namespace std;
vector<int> path;
vector<vector<int>> result;
void dfs(const vector<vector<int>>& graph , int x, int n)
{if(x==n){result.push_back(path);return;}for(int i = 1 ; i <=n ; i++){if(graph[x][i]==1){path.push_back(i);dfs(graph,i,n);path.pop_back();}}
}int main()
{int n,m,s,t;cin>> n >> m;//构造图vector<vector<int>> graph(n+1,vector<int>(n+1,0));while(m--){cin>>s>>t;graph[s][t] =1;}//开始搜索,因为是从节点1出发,因此先加入节点1path.push_back(1);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;    //最后一个元素单独打印}return 0;
}

邻接表(构造和遍历方式有所不同)

#include<bits/stdc++.h>
using namespace std;
vector<int> path;
vector<vector<int>> result;
void dfs(const vector<list<int>>& graph , int x, int n)
{if(x==n){result.push_back(path);return;}for(int i : graph[x])        //这里是和邻接矩阵不同的地方,遍历方式{path.push_back(i);dfs(graph,i,n);path.pop_back();}
}int main()
{int n,m,s,t;cin>> n >> m;//构造图vector< list<int> > graph(n+1);while(m--){cin>>s>>t;graph[s].push_back(t);    //下标对应节点}//开始搜索,因为是从节点1出发,因此先加入节点1path.push_back(1);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;    //最后一个元素单独打印}return 0;
}

广搜理论基础

广搜理论基础

相关文章:

代码随想录算法训练营第六十四天 | 图论理论基础、深搜理论基础、广搜理论基础、98. 所有可达路径

图论理论基础 我写在了个人语雀笔记中 https://www.yuque.com/yuqueyonghu8mml9e/bmbl71/ex473q4y0ebs0l3r?singleDoc# 深搜理论基础 https://www.yuque.com/yuqueyonghu8mml9e/bmbl71/zamfikz08c2haptn?singleDoc# 98. 所有可达路径 题目链接&#xff1a;98. 所有可达…...

【教师资格证考试综合素质——法律专项】教师法笔记以及练习题

《中华人民共和国教师法》 一&#xff0e;首次颁布&#xff1a;第一部《中华人民共和国教师法》于1993年10月31日由第八届全国人民代表大会常务委员会第四次会议通过&#xff0c;1994年1月1日起执行。 二&#xff0e;历次修改&#xff1a;2009年8月27日第十一届全国人民代表…...

图卷积网络(Graph Convolutional Network, GCN)

图卷积网络&#xff08;Graph Convolutional Network, GCN&#xff09;是一种用于处理图结构数据的深度学习模型。GCN编码器的核心思想是通过邻接节点的信息聚合来更新节点表示。 图的表示 一个图 G通常表示为 G(V,E)&#xff0c;其中&#xff1a; V 是节点集合&#xff0c;…...

【diffusers 极速入门(一)】pipeline 实际调用的是什么? __call__ 方法!

在使用 diffusers 库进行图像生成时&#xff0c;你可能会发现管道&#xff08;pipeline&#xff09;对象可以像函数一样被调用。这背后的魔法是什么呢&#xff1f;答案是&#xff1a;__call__ 方法&#xff01;本文将通过简单的案例代码&#xff0c;带你快速了解 diffusers 管道…...

【DPDK学习路径】二、DPDK简介

DPDK(Data Plane Development Kit)是一个框架&#xff0c;用于快速报文处理。 在linux内核提供的报文处理模型中&#xff0c;接收报文的处理路径为&#xff1a;首先由网卡硬件接收&#xff0c;产生硬中断&#xff0c;触发网卡驱动程序注册的中断函数处理&#xff0c;之后产生软…...

python基础 002 - 2 常用数据类型

python的常用数据类型 int , 整型 1,2,3float ,小数&#xff0c;浮点类型1.2bool , boolean 布尔&#xff0c;真假。判断命题。True Flasestr &#xff0c;字符串 list , 列表 a []tuple, 元组 a ()dict , dictionary, 字典 a {}set , 集合 a {} 1 查看数据类型 typ…...

爆赞!GitHub首本Python开发实战背记手册,标星果然百万名不虚传

Python (发音:[ paiθ(ə) n; (US) paiθɔn ] n. 蟒蛇&#xff0c;巨蛇 )&#xff0c;是一种面向对象的解释性的计算机程序设计语言&#xff0c;也是一种功能强大而完善的通用型语言&#xff0c;已经具有十多年的发展历史&#xff0c;成熟且稳定。Python 具有脚本语言中最丰富…...

Spring源码-xxxAware实现类和BeanPostProcessor接口调用过程

xxxAware实现类作用 以ApplicationContextAware接口为例 ApplicationContextAware的作用是可以方便获取Spring容器ApplicationContext&#xff0c;从而可以获取容器内的Bean package org.springframework.context;import org.springframework.beans.BeansException; import or…...

Uni-app x

uni-app x&#xff0c;是下一代 uni-app&#xff0c;是一个跨平台应用开发引擎。 uni-app x 是一个庞大的工程&#xff0c;它包括uts语言、uvue渲染引擎、uni的组件和API、以及扩展机制。 uts是一门类ts的、跨平台的、新语言。uts在iOS端编译为swift、在Android端编译为kotli…...

Python 基础:文件

目录 一、从文件中读取数据1.1 读取整个文件1.2 逐行读取 二、写入文件2.1 写入空文件2.2 写入多行2.3 附加到文件 遇到看不明白的地方&#xff0c;欢迎在评论中留言呐&#xff0c;一起讨论&#xff0c;一起进步&#xff01; 本文参考&#xff1a;《Python编程&#xff1a;从入…...

WebForms 母版页

WebForms 母版页 介绍 WebForms 母版页是 ASP.NET WebForms 应用程序中的一项功能&#xff0c;它允许开发人员创建一个包含页面布局和控件的模板&#xff0c;其他页面可以继承这个模板。使用母版页可以确保整个网站的一致性和减少重复代码。 如何创建母版页 在 Visual Stud…...

Java应用打包成Docker镜像

# 使用官方的OpenJDK17镜像作为基础镜像 FROM openjdk:17 # 设置工作目录 WORKDIR /app # 复制本地的Java应用程序文件到镜像中的指定目录 COPY target/bear-module-system-0.0.1-SNAPSHOT.jar /app/bear-module-system-0.0.1-SNAPSHOT.jar # 暴露API端口 EXPOSE 8888 …...

什么是自动驾驶中的CopyCat?

"CopyCat"这个词通常有两个含义: 字面意思:它可以指一个模仿别人的人,就像猫一样模仿其他猫的行为。在日常用语中,如果有人说某人是个"copycat",他们可能是在说这个人缺乏原创性,总是模仿别人的想法、风格或者行为。 心理学和犯罪学中的含义:在心…...

为什么没人详细说过智能猫砂盆?最受欢迎的好用智能猫砂盆解析!

不知道大家有没有发现&#xff0c;在快节奏的现代生活中&#xff0c;忙碌于上班的我们会发现自己越来越难以抽出足够的时间去细心照料自己的猫咪。每次下班回家&#xff0c;看到猫砂盆里堆积的粪便和尿液&#xff0c;自己都感到一阵头痛。这时&#xff0c;我开始考虑起智能猫砂…...

AI视频智能监管赋能城市管理:打造安全有序的城市环境

一、方案背景 随着城市化进程的加速和科技的飞速发展&#xff0c;街道治安问题日益凸显&#xff0c;治安监控成为维护社会稳定和保障人民安全的重要手段。当前&#xff0c;许多城市已经建立了较为完善的治安监控体系&#xff0c;但仍存在一些问题。例如&#xff0c;监控设备分…...

多态性(Java)

本篇学习面向对象语言的第三个特性——多态。 目录 1、多态的概念 2、继承多态实现条件 3、重写 4、重新与重载的区别&#xff1a; 5、向上转移和向下转型 5、1向上转型&#xff1a; 5、2 向下转型 1、多态的概念 多态的概念&#xff1a;通俗来说&#xff0c;就是多种形态…...

国际期货行情相关术语

1&#xff09;合约&#xff1a;期货行情表提供了期货交易的相关信息 &#xff0c;行情表中每一个期货合约都有合约代码&#xff08;由期货合约交易代码和合约到期月份组成&#xff09;来标识。 &#xff08;2&#xff09;开盘价&#xff1a;当日某一期货合约交易开始前五分钟集…...

LeetCode20.有效的括号

题目描述 分析 我们刚上来的思路可能是&#xff1a;找出这三种括号的个数 如果都是偶数 说明匹配 但是这里还有一个顺序问题 比如 " )( "这样是不匹配的&#xff01; 所以这种思路不可取&#xff01; 我们想 如果遇到左括号&#xff0c;把他读到一个顺序表中&#…...

尚玩助手广告变现app开发

尚玩助手广告变现app的开发涉及到多个关键环节。首先&#xff0c;市场调研与定位是不可或缺的步骤&#xff0c;通过了解当前市场上流行的小游戏类型、用户偏好以及竞争对手的情况&#xff0c;来确定app的定位和目标用户群体。 其次&#xff0c;游戏设计与规划也是关键的一环&a…...

Anti-human IL-10 mAb (12G8), biotin:Mabtech热销品

Anti-human IL-10 mAb (12G8), biotin该单克隆抗体能够在ELISpot、FluoroSpot和ELISA等免疫分析方法中特异性检测人白介素10&#xff08;IL-10&#xff09;。可以将该单克隆抗体12G8作为检测抗体与单克隆抗体9D7&#xff08;ca#3430-3&#xff09;作为捕获抗体配对用于ELISpot、…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...