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

算法训练营64-图论-深度优先优先搜索(dfs)-广度优先搜索(bfs)

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

邻接矩阵表示图

#include<bits/stdc++.h>using namespace std;vector<vector<int>> reslut;
vector<int> path;void dfs(vector<vector<int>>& map, int start, int end) {if(start == end) {reslut.push_back(path);return;}for(int i = 1;i < map.size();i++) {if(map[start][i] == 1) {path.push_back(i);dfs(map, i, end);path.pop_back();}}
}int main() {int n, m;cin >> n >> m;vector<vector<int>> map(n + 1, vector<int>(n + 1, 0));for(int i = 0;i < m;i++) {int x,y;cin >> x >> y;map[x][y] = 1;}path.push_back(1);dfs(map, 1, n);if(reslut.size() == 0) cout << -1 << endl;else {for(int i = 0;i < reslut.size();i++) {for(int j = 0;j < reslut[i].size() - 1;j++) {cout << reslut[i][j] << ' ';}cout << reslut[i][reslut[i].size() - 1] << endl;}}return 0;
}

邻接表表示图:

#include <iostream>
#include <vector>
#include <list>using namespace std;vector<vector<int>> result;
vector<int> path;void dfs(vector<list<int>>& map, int x, int n) {if(x == n) {result.push_back(path);return;}for(int i : map[x]) {path.push_back(i);dfs(map, i, n);path.pop_back();}
}int main() {int n, m, x, y;cin >> n >> m;vector<list<int>> graph(n + 1);while(m--) {cin >> x >> y;graph[x].push_back(y);}path.push_back(1);dfs(graph, 1, n);if(result.size() == 0) cout << -1 << endl;else {for(int i = 0;i < result.size();i++) {int size = result[i].size();for(int j = 0;j < size - 1;j++) {cout << result[i][j] << ' ';}cout << result[i][size - 1] << endl;}        }return 0;
}

相关文章:

算法训练营64-图论-深度优先优先搜索(dfs)-广度优先搜索(bfs)

题目&#xff1a;98. 所有可达路径 (kamacoder.com) 邻接矩阵表示图 #include<bits/stdc.h>using namespace std;vector<vector<int>> reslut; vector<int> path;void dfs(vector<vector<int>>& map, int start, int end) {if(start…...

kotlin函数

1、函数定义 // 下边定义了main函数 fun main() {} 2、函数的类型 // foo函数定义 fun foo () {} // 对应无参类型 () -> Unit fun foo (a: Int):String {} // 对应有参类型 (Int) -> String 3、函数的引用 函数的引用类似C语言中的函数指针&#xff0c;可用于函数传…...

深入理解计算机系统 CSAPP 家庭作业7.12

A:refptr (unsigned)(ADDR(r.symbol) r.addend - refaddr) 0x4004f8 (-4) - 0x4004ea 0xa B:refaddr 0x4004d0 0xa 0x4004da refptr 0x400500 (-4) - 0x4004da 0x22 ​​​​​​​...

Batch脚本中的环境变量沙盒:setlocal与endlocal全解析

Batch脚本中的环境变量沙盒&#xff1a;setlocal与endlocal全解析 在Windows的批处理&#xff08;Batch&#xff09;脚本世界中&#xff0c;setlocal和endlocal是两个至关重要的命令&#xff0c;它们为脚本中环境变量的修改提供了一个隔离的环境。这就像是为变量创建了一个临时…...

AI引领创意潮流:高效生成图片,参考图助力,一键保存到指定文件夹

在这个数字与创意交融的时代&#xff0c;我们迎来了AI绘画的新纪元。借助先进的AI技术&#xff0c;我们不仅能够高效生成图片&#xff0c;还能在参考图的启发下&#xff0c;激发无限创意&#xff0c;让您的想象力在数字世界中自由翱翔。 首助编辑高手软件中的魔法智能绘图板块&…...

ADOP带你了解:数据中心的高速互联解决方案

随着大语言模型和AIGC的飞速发展&#xff0c;数据中心对于高速、高可靠性的网络连接需求日益增长。ADOP系列产品正是在这样的背景下应运而生&#xff0c;为现代数据中心提供了全面的连接解决方案。 ADOP系列产品概览 ADOP系列产品旨在为云、高性能计算、Web 2.0、企业、电信、…...

使用SpringBoot整合Servlet

一、SpringBoot和Servlet的整合 1、用注解WebServlet配置Servlet映射 创建一个SpringBoot的web工程&#xff0c;在工程用创建一个Servlet 2、在SpringBoot的启动类上加注解ServletComponentScan 二、额外的方式 1、不使用WebServlet配置Servlet映射 创建一个SpringBoot工…...

vue引入eachrts

1. 安装Echarts 使用npm npm install echarts --save 导入Echarts插件 import echarts from echarts Vue.prototype.$echarts echarts import echarts from echarts 我们来做个简单的实例首先需要一个容器装下Echarts <template><div id"list"…...

c++ 智能指针实战分析

一.智能指针的设计思路 智能指针是类模板&#xff0c;再栈上创建智能指针对象。把普通指针交给智能指针对象。智能指针对象过期时&#xff0c;调用析构函数释放普通指针的内存。 智能指针的类型 auto_ptr是C98的标准&#xff0c;c17已经弃用。unique_ptr、shared_ptr和weak_…...

3D Web轻量引擎HOOPS Web Platform赋能AEC行业数字化,高效渲染与多格式支持!

在建筑、工程和施工&#xff08;AEC&#xff09;行业&#xff0c;数字化转型和高效协作正变得越来越重要。为应对日益复杂的项目需求和不断提升的质量标准&#xff0c;AEC企业需要一种强大的工具来实现高效的3D可视化和数据管理。HOOPS Web Platform作为一款综合性3D开发平台&a…...

学术英语写作为什么会成为留学生的压力?

对留学党来说&#xff0c;从出国前的标准化测试、申请文书&#xff0c;到留学后的学业要求&#xff0c;都需要用到学术英语写作。可以说&#xff0c;学术英语写作对留学生涯有着重要影响。 然而&#xff0c;这却是令很多中国学生头疼的问题&#xff0c;中国学生往往在数学、物…...

docker 安装达梦8

背景 X86-64架构使用Docker安装dm8_20240422_x86_rh6_64_rq_std_8.1.3.100_pack2.tar 1.下载Docker安装包 达梦官网下载dm8_20240422_x86_rh6_64_rq_std_8.1.3.100_pack2.tar安装包 快速下载通道&#xff1a; 达梦镜像包 2.将安装包上传至服务器&#xff0c;并加载镜像 拷…...

npm常用命令大全(非常详细)

npm&#xff08;Node Package Manager&#xff09;是Node.js的包管理工具&#xff0c;它允许你安装、更新、删除和管理Node.js项目的依赖。 以下是npm的一些常用命令&#xff0c;按照不同的功能进行分类和解释&#xff1a; 1. 初始化项目 init # 初始化一个新的npm项目&…...

东西方文化与管理探讨汉捷咨询汉捷咨询

东西方文化的发展不同&#xff0c;对于管理实践的影响也不相同。汉捷咨询从东西方文化的差异以管理体系的差异进行深层次分析&#xff0c;希望这些分析对企业家的管理实践起到良好的启发作用。 东西方文化的差异 东西方人在思维方式上存在的差异&#xff0c;其根源是什么呢&a…...

行业案例 | 智能终端设备的数据基础从哪儿来?

智能终端的快速发展让我们在许多科幻电影中看到的“未来场景”正在一步步变为现实&#xff1a;智能家居正在解放我们的双手&#xff0c;工业机器人让生产效率倍增&#xff0c;智能穿戴设备让我们便利地感知自身与外部的连结……然而&#xff0c;要想让万物“智联”&#xff0c;…...

《Windows API每日一练》6.1 鼠标基础知识

本节我们讲述鼠标的一些基础知识。 本节必须掌握的知识点&#xff1a; 鼠标 6.1.1 鼠标 鼠标是1964年由Douglas Engelbart发明的&#xff0c;用来取代由键盘输入的繁琐指令&#xff0c;简化电脑操作。早期的鼠标是单键鼠标&#xff0c;只有一个键&#xff0c;后来逐步改进为双…...

闹大了!OpenAI 宣布终止提供API服务

事件背景&#xff1a; OpenAI宣布终止对中国提供API服务&#xff0c;影响中国大陆的API开发者。受影响的开发者收到OpenAI的警告信&#xff0c;要求7月9日后停止服务。 OpenAI的业务和营收&#xff1a; 2023年营收16亿美元&#xff0c;2024年上半年年化营收达34亿美元。营收来…...

java里的空接口实现它有什么用?

我们在看源码时&#xff0c;经常会看到一些空接口&#xff0c;这些空接口里没有一个方法&#xff0c;实现它有什么作用呢&#xff1f;让我们先找几个常见的空接口看看。 一、Serializable接口 在Java中&#xff0c;一个常见的空接口就是java.io.Serializable。 public inter…...

Spring的jar包下载(最新版6.0版本)

1.在Spring官网的projects下面点击spring-framework 2.进入github官网 3.进入github后往下滑&#xff0c;点击Spring Framework Artifacts 4.往下滑找到 点击 5.在左边先点击Artifacts&#xff0c;在右边找到 libs-snapshot&#xff0c;展开libs-snapshot&#xff08;之前其他…...

解决Java中数据库连接泄露的技术

解决Java中数据库连接泄露的技术 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 介绍 在Java应用程序中&#xff0c;数据库连接的泄露是一个常见且影响性能的…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

使用SSE解决获取状态不一致问题

使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件&#xff0c;这个上传文件是整体功能的一部分&#xff0c;文件在上传的过程中…...