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

DFS寻找从s到t的所有路径

问题描述:

输入一个有向图,输出从s到t的所有路径的结点

输入:
3 3
0 1
1 2
0 2
输出:

0 1 2

0  2

代码:

#include<bits/stdc++.h>
using namespace std;const int N = 103;
vector<int>e[N];//用行为N的,列为可变长度的二维数组表示邻接表 
bool vis[N];//定义访问标记数组 
int path[N],cnt;//path用于记录路径,cnt用于记录路径长度(cnt初值为0,全局变量默认为0)
int n,m;//n为结点数,m为边数 void dfs(int s,int t){//找到从s到t的所有路径vis[s] = 1;//第一件事永远都是把当前结点置为已访问path[cnt++] = s;//把当前结点加入路径中 if(s==t){//如果找到一条从s到t的路径for(int i=0;i<cnt;++i){printf("%d ",path[i]);//打印路径}printf("\n");vis[s] = 0;//回溯操作,如果不回溯,则结果只能找到一条从s到t的路径 cnt--;//回溯 return;}for(int i=0;i<e[s].size();++i){//如果当前还没找到s到t路径,继续访问当前s的下一个邻接点   e.[s].size表示,当前结点s的邻接点的个数 if(!vis[e[s][i]]){//如果第s行,第i个结点没有被访问过,则继续访问 dfs(e[s][i],t);//继续从当前扫描到的结点出发去寻找到t的路径 }}vis[s]=0;//回溯,如果没有找到路径,也要回溯,因为如果访问过s之后,就无法再访问当前这个s结点了,也只会找到一条路径 cnt--;
}int main(void){while(~scanf("%d%d",&n,&m)&&(n||m)){//输入结点数n和边数m for(int i=0;i<n;++i){e[i].clear();//把邻接表中每一行的节点数清空,相当于初始化邻接表 } for(int i=0;i<m;++i){//输入边 int x,y;scanf("%d%d",&x,&y);e[x].push_back(y);//如果是有向图,只需要在x后面连上y即可 //	e[y].push_back(x);如果是无向图,同样也要在y结点后面加上x } dfs(0,n-1);}return 0;
}

相关文章:

DFS寻找从s到t的所有路径

问题描述&#xff1a; 输入一个有向图&#xff0c;输出从s到t的所有路径的结点 输入&#xff1a; 3 3 0 1 1 2 0 2输出&#xff1a; 0 1 2 0 2 代码&#xff1a; #include<bits/stdc.h> using namespace std;const int N 103; vector<int>e[N];//用行为N的…...

分享!JetBrains IDE中的GitLab支持

GitLab是流行的基于git的软件开发和部署平台之一&#xff0c;虽然很长一段时间以来&#xff0c;所有基本git操作都已经可以通过GitLab实现&#xff0c;但GitLab集成仍是JetBrains社区的一大最热门请求。为此&#xff0c;JetBrains团队今年与GitLab联手提供了这种类型的集成。 …...

jq弹窗拖动改变宽高

预览效果 <div classtishiMask><div class"tishiEm"><div id"coor"></div><div class"topNew ismove"><span class"ismove">提示</span><p onclick"closeTishi()"></p&…...

时间不确定度在分布式系统中的说明

On the one hand 时间不确定度问题和影响在分布式系统中 说明 时钟不确定度&#xff08;Clock Uncertainty&#xff09;是指在分布式系统中&#xff0c;由于网络延迟、时钟漂移等因素导致系统中各个节点时钟的不同步现象。这种不同步可能会影响到分布式系统的一致性和正确性…...

VMware vCenter 从6.7跨版本升级至7.0U3N

本文尝试使用 vCenter Server Appliance 管理界面 (VAMI) 进行对vCenter Server Appliance7应用进行小版本升级&#xff0c;从6.7.0.47000升级到7.0.3.01600&#xff08;7.0U3N&#xff09;。 一、升级前的准备工作 1、检查当前运行环境&#xff08;当前为6.7.0.47000&#x…...

大麦订单生成器最新版 大麦订单一键生成截图

1.可以一键添加&#xff0c;生成的假订单没有水印&#xff0c;界面也很真实。 2.在软件中输入生成的信息&#xff0c;这是产品信息&#xff0c;选择生成的产品图像&#xff0c;最后生成它。 后台一键生成&#xff0c;独立后台管理 教程&#xff1a;解压源码&#xff0c;修改数…...

如何对Map集合的key进行大小写转换?

工具类&#xff1a; ToUpperCaseKeyMapUtil.java public class ToUpperCaseKeyMapUtil {//对单一的mappublic static <T> Map<String, T> toUpperCaseKeyMap(Map<String, T> map) {if (map ! null) {List<String> mapKeyList new ArrayList<>…...

将函数实现放到CPP报“无法解析的外部符号...”,系VS Bug

发现一个现象&#xff0c;就是项目中有一个类&#xff0c;如果将函数实现全部放到头文件中&#xff0c;编译不报错&#xff0c;如果将函数实现放到CPP中则始终提示“无法解析的外部符号...”&#xff0c;考虑到放到头文件中能正常编译运行&#xff0c;显然这里不符合“无法解析…...

异步FIFO设计的仿真与综合技术(3)

概述 本文主体翻译自C. E. Cummings and S. Design, “Simulation and Synthesis Techniques for Asynchronous FIFO Design 一文&#xff0c;添加了笔者的个人理解与注释&#xff0c;文中蓝色部分为笔者注或意译。前文链接&#xff1a; 异步FIFO设计的仿真与综合技术&#xf…...

什么是区块链,解释区块链的原理和应用场景

1、什么是区块链&#xff0c;解释区块链的原理和应用场景。 区块链是一种分布式数据库&#xff0c;它由一系列按照时间顺序排列的数据块组成&#xff0c;并采用密码学方式保证不可篡改和不可伪造。区块链技术最初起源于比特币&#xff0c;作为比特币的底层技术&#xff0c;用于…...

使用bert进行文本二分类

构建BERT&#xff08;Bidirectional Encoder Representations from Transformers&#xff09;的训练网络可以使用PyTorch来实现。下面是一个简单的示例代码&#xff1a; import torch import torch.nn as nn from transformers import BertModel, BertTokenizer# Load BERT to…...

用Windows Installer CleanUp Utility 在windows server上面将软件卸载干净,比如SQLSERVER

这里写自定义目录标题 下载文件&#xff1a;Windows Installer CleanUp Utility。 通过以上工具可以将一个应用程序卸载干净。...

Java手写LinkedList和拓展

Java手写LinkedList和拓展 思维导图 #mermaid-svg-K0RTlFFvnikDRvqp {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-K0RTlFFvnikDRvqp .error-icon{fill:#552222;}#mermaid-svg-K0RTlFFvnikDRvqp .error-text{fill…...

机器学习(14)---逻辑回归(含手写公式、推导过程和手写例题)

逻辑回归 一、逻辑回归概述二、模型、策略和优化&#xff08;手写&#xff09;三、w和b的梯度下降公式推导四、例题分析4.1 题目4.2 解答 一、逻辑回归概述 1. 逻辑回归也称作logistic回归分析&#xff0c;是一种广义的线性回归分析模型&#xff0c;属于机器学习中的监督学习。…...

LLFormer 论文阅读笔记

Ultra-High-Definition Low-Light Image Enhancement: A Benchmark and Transformer-Based Method 这是南京大学在AAAI 2023发表的一篇AAAI2023 超高清图像暗图增强的工作。提出了一个超高清暗图增强数据集&#xff0c;提供了4K和8K的图片&#xff0c;同时提出了一个可用于暗图…...

JSP语法基础习题

目录 简答题&#xff1a;jsp中静态include和动态include的区别是什么&#xff1f; 简答题&#xff1a;jsp有哪些内置对象&#xff0c;作用分别是什么&#xff1f; 简答题&#xff1a;Request对象的主要方法有哪些&#xff1f; 代码题&#xff1a; 简答题&#xff1a;jsp中静态…...

vue类与样式的绑定列表渲染

目录 1.类与样式的绑定 1.1绑定 HTML class 1.2绑定数组 1.3绑定内联样式 绑定数组 2.列表渲染 2.1v-for​ 2.2v-for 与对象 2.3在 v-for 里使用范围值​ 1.类与样式的绑定 1.1绑定 HTML class 我们可以给 :class (v-bind:class 的缩写) 传递一个对象来动态切换 class…...

vue3+element-plus权限控制实现(el-tree父子级不关联情况处理)

文章目录 前言一、遇到的交互场景el-tree 中 check-strictly 属性 二、处理父级的半选中以及选中交互el-treecheck&#xff0c;check-change 事件编辑进来&#xff0c;父级的半选状态处理 总结 前言 在开发后台管理系统的时候&#xff0c;用户的权限控制是一个常见的需求。这里…...

js中事件委托和事件绑定之间的区别

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 事件绑定&#xff08;Event Binding&#xff09;⭐事件委托&#xff08;Event Delegation&#xff09;⭐ 选择事件绑定或事件委托⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本…...

Android 11.0 系统system模块开启禁用adb push和adb pull传输文件功能

1.使用场景 在进行11.0的系统定制化开发中,在一些产品中由于一些开发的功能比较重要,防止技术点外泄在出货产品中,禁用 adb pull 和adb push等命令 来获取系统system下的jar 和apk 等文件,所以需要禁用这些命令 2.系统system模块开启禁用adb push和adb pull传输文件功能的…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...

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

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

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

如何配置一个sql server使得其它用户可以通过excel odbc获取数据

要让其他用户通过 Excel 使用 ODBC 连接到 SQL Server 获取数据&#xff0c;你需要完成以下配置步骤&#xff1a; ✅ 一、在 SQL Server 端配置&#xff08;服务器设置&#xff09; 1. 启用 TCP/IP 协议 打开 “SQL Server 配置管理器”。导航到&#xff1a;SQL Server 网络配…...