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

代码随想录-算法训练营-番外(图论01:图论理论基础,所有可到达的路径)

day01 图论part01 
今日任务:图论理论基础/所有可到达的路径
代码随想录图论视频部分还没更新
https://programmercarl.com/kamacoder/图论理论基础.html#图的基本概念

day01

所有可达路径

邻接矩阵

 import java.util.Scanner;import java.util.List;import java.util.ArrayList;​public class Main{static List<List<Integer>> result = new ArrayList<>();static List<Integer> path = new ArrayList<>();public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] graph = new int[n + 1][n + 1];for(int i = 0; i < m; i++){graph[sc.nextInt()][sc.nextInt()] = 1;}path.add(1); //先加一个节点dfs(graph, 1, n); if (result.isEmpty()) System.out.println(-1);for(List<Integer> pa : result){for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));} }private static void dfs(int[][] graph, int x, int n){//n就是结束节点if(x == n){result.add(new ArrayList(path));return;}for(int i = 1; i <= n; i++){if (graph[x][i] == 1) { path.add(i); dfs(graph, i, n); path.remove(path.size() - 1); }}return;}}

邻接表

 //感觉graph不用LinkedList而是直接用ArrayList也可以,因为这个场景下不涉及什么增删改而基本都是访问import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Scanner;​public class Main {static List<List<Integer>> result = new ArrayList<>(); // 收集符合条件的路径static List<Integer> path = new ArrayList<>(); // 1节点到终点的路径​public static void dfs(List<LinkedList<Integer>> graph, int x, int n) {if (x == n) { // 找到符合条件的一条路径result.add(new ArrayList<>(path));return;}for (int i : graph.get(x)) { // 找到 x指向的节点path.add(i); // 遍历到的节点加入到路径中来dfs(graph, i, n); // 进入下一层递归path.remove(path.size() - 1); // 回溯,撤销本节点}}​public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();​// 节点编号从1到n,所以申请 n+1 这么大的数组List<LinkedList<Integer>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new LinkedList<>());}​while (m-- > 0) {int s = scanner.nextInt();int t = scanner.nextInt();// 使用邻接表表示 s -> t 是相连的graph.get(s).add(t);}​path.add(1); // 无论什么路径已经是从1节点出发dfs(graph, 1, n); // 开始遍历​// 输出结果if (result.isEmpty()) System.out.println(-1);for (List<Integer> pa : result) {for (int i = 0; i < pa.size() - 1; i++) {System.out.print(pa.get(i) + " ");}System.out.println(pa.get(pa.size() - 1));}}}

感谢大佬分享:

代码随想录算法训练营第五十天|Day50 图论_本关任务:创建邻接表存储的无向图,并输出图的邻接表。-CSDN博客

相关文章:

代码随想录-算法训练营-番外(图论01:图论理论基础,所有可到达的路径)

day01 图论part01 今日任务:图论理论基础/所有可到达的路径 代码随想录图论视频部分还没更新 https://programmercarl.com/kamacoder/图论理论基础.html#图的基本概念 day01 所有可达路径 邻接矩阵 import java.util.Scanner;import java.util.List;import java.util.ArrayL…...

【JAVA】Java项目实战—Java EE项目:企业资源规划(ERP)系统

在企业管理中&#xff0c;企业资源规划&#xff08;ERP&#xff09;系统是不可或缺的工具。它能够帮助企业高效管理各种资源&#xff0c;包括人力资源、财务资源和库存等。Java作为一种成熟的编程语言&#xff0c;因其跨平台特性、强大的生态系统以及良好的社区支持&#xff0c…...

springboot配置过滤器解决html资源路径和接口路径冲突问题

比如&#xff1a; html文件使用 / 接口路径使用 /api 首先配置文件里肯定配置范围最大的根路径 server:port: 80servlet:context-path: / 过滤器代码 Slf4j public class RequestSeparationFilter implements Filter {Overridepublic void init(FilterConfig filterConfi…...

在IDE中使用Git

我们在开发的时候肯定是经常使用IDE进行开发的&#xff0c;所以在IDE中使用Git也是非常常用的&#xff0c;接下来以IDEA为例&#xff0c;其他的VS code &#xff0c;Pycharm等IDE都是一样的。 在IDEA中配置Git 1.打开IDEA 2.点击setting 3.直接搜索git 如果已经安装了会自…...

【AIGC进阶-ChatGPT提示词副业解析】反向心理学在沟通中的运用:激将法的艺术

引言 在日常沟通和管理中&#xff0c;直接的表达方式并不总能达到预期效果。反向心理学&#xff0c;特别是其中的激将法&#xff0c;作为一种独特的沟通技巧&#xff0c;往往能在看似消极的表达中激发出积极的反应。本文将深入探讨反向心理学中激将法的运用技巧、实施策略及其…...

JeecgBoot passwordChange 任意用户密码重置漏洞复现

0x01 产品简介 Jeecg Boot是一个企业级低代码开发平台,基于前后端分离的架构,融合了SpringBoot、SpringCloud、Ant Design、Vue、Mybatis-plus、Shiro、JWT等多种主流技术,旨在帮助企业快速构建各种应用系统,提高开发效率,降低开发成本。采用最新主流的前后分离框架,使得…...

【智体OS】官方上新发布智体机器人:使用rtrobot智体应用远程控制平衡车机器人

【智体OS】官方上新发布智体机器人&#xff1a;使用rtrobot智体应用远程控制平衡车机器人 dtns.network是一款主要由JavaScript编写的智体世界引擎&#xff08;内嵌了three.js编辑器的定制版-支持以第一视角浏览3D场馆&#xff09;&#xff0c;可以在浏览器和node.js、deno、e…...

Blazor(.razor)+VUE+elementUI适合一起用吗

在实际项目中&#xff0c;将 Blazor&#xff08;.razor&#xff09; 与 Vue.js 和 ElementUI 一起使用是可以实现的&#xff0c;但是否适合取决于你的项目需求、开发团队的技术栈和具体场景。以下是对这种组合的详细分析&#xff1a; 一、适合一起使用的场景 1.1 逐步引入 Bla…...

SpringBoot左脚进门之Maven管理家

一、概念 Maven 是一个项目管理和整合工具。通过对 目录结构和构建生命周期 的标准化&#xff0c; 使开发团队用极少的时间就能够自动完成工程的基础构建配置。 Maven 简化了工程的构建过程&#xff0c;并对其标准化&#xff0c;提高了重用性。 Maven 本地仓库 (Local Reposi…...

188-下翻便携式6U CPCI工控机箱

一、板卡概述 下翻式CPCI便携工控机,系统采用6u cpci背板结构,1个系统槽,7个扩展槽, 满足对携带的需求,可装标准6U8槽CPCI主板,8个扩展槽, 满足客户对空间扩展的需求.可宽温服务的工作产品,15高亮度液晶显示屏,超薄88键笔记本键盘,触摸式鼠标,加固型机箱结构,使它能够适应各种复…...

Ubuntu 挂载目录

1. 临时挂载&#xff08;重启后失效&#xff09; 创建挂载点&#xff1a; $ sudo mkdir -p /work临时挂载磁盘到 work 目录&#xff1a; $ sudo mount /dev/nvme0n1p1 /work验证挂载是否成功&#xff1a; $ df -h /work此方法挂载在系统重启后会失效&#xff0c;需手动重新挂载…...

基于IEEE 802.1Qci的时间敏感网络(TSN)主干架构安全分析及异常检测系统设计

中文标题&#xff1a;基于IEEE 802.1Qci的时间敏感网络&#xff08;TSN&#xff09;主干架构安全分析及异常检测系统设计 英文标题&#xff1a;Security Analysis of the TSN Backbone Architecture and Anomaly Detection System Design Based on IEEE 802.1Qci 作者信息&…...

2024年食堂采购系统源码技术趋势:如何开发智能的供应链管理APP

本篇文章&#xff0c;小编将与大家一同探讨2024年食堂采购系统的技术趋势&#xff0c;并提供开发更智能的供应链管理APP的策略。 一、2024年食堂采购系统的技术趋势 1.人工智能与机器学习的深度应用 在2024年&#xff0c;AI和机器学习在食堂采购系统中的应用将更加普遍。这些…...

zotero安装教程(包括茉莉花插件)

zotero安装教程&#xff08;包括茉莉花插件&#xff09; zotero下载(windows)1-安装 Zotero2-安装 Zotero Connector3-安装浏览器插件--jasminum茉莉花功能&#xff1a;插件下载地址&#xff1a;[https://github.com/search?qjasminum&typerepositories](https://github.c…...

webpack4 - 配置文件分离(详细教程)

webpack根据开发和生成环境一般可以将配置文件拆分&#xff0c;拆分dev和prod两种环境 |- package.json|- /build|- webpack.base.js|- webpack.dev.js|- webpack.prod.js在scripts里修改相应的命令 "dev": "webpack-dev-server --config build/webpack.dev.j…...

MongoDB 分片

MongoDB 分片 MongoDB 分片是一种数据库架构&#xff0c;用于将大量数据分布存储在多个服务器上。这种设计允许数据库扩展&#xff0c;以处理大量数据和高吞吐量操作。分片通过将数据集分割成小块&#xff0c;称为分片&#xff0c;并将这些分片分布到多个服务器上来工作。每个…...

PHP加载MySQL扩展

PHP本身不具备操作MySQL数据库的能力&#xff0c;需要借助PHP操作MySQL的扩展来实现 1、PHP加载MySQL扩展&#xff1a;php.ini文件中 2、PHP中所有的扩展都在ext文件中&#xff0c;需要指定扩展所在路径&#xff1a;extension_dir 3、php.ini 已经被apache加载&#xff0c;所以…...

期末复习-计算机网络篇SCAU

第一章&#xff1a;概述 1.计算机网络的特点&#xff0c;互联网发展的三个阶段 特点&#xff1a;连通性、资源共享 三个阶段&#xff1a; 1969-1990&#xff1a;从单个网络ARPANET向互联网发展 1985-1993&#xff1a;建成了三级结构的互联网 1993-现在&#xff1a;全球范…...

使用LLM进行股价预测(附代码)

使用LLM进行股价预测(附代码) 注意 代码是完整的&#xff0c;但是需要 https://github.com/wxy2ab/akinterpreter 才能完整运行 利用 Python 和 AkShare 进行股票数据分析与预测&#xff1a;以中远海控为例 在本文中&#xff0c;我们将使用 Python 的 akshare 库获取中远海…...

分支限界笔记

文章目录 概要整体架构流程基本概念分支限界法的定义核心思想 简单问题介绍问题&#xff1a;简单背包问题思考&#xff1a;暴力解法聪明的解法&#xff1a;分支限界法直观理解分支限界法的步骤0-1背包问题问题描述问题建模问题分析1. 定义问题的解空间&#xff0c;确定易于搜索…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...