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的所有路径
问题描述: 输入一个有向图,输出从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的…...
分享!JetBrains IDE中的GitLab支持
GitLab是流行的基于git的软件开发和部署平台之一,虽然很长一段时间以来,所有基本git操作都已经可以通过GitLab实现,但GitLab集成仍是JetBrains社区的一大最热门请求。为此,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 时间不确定度问题和影响在分布式系统中 说明 时钟不确定度(Clock Uncertainty)是指在分布式系统中,由于网络延迟、时钟漂移等因素导致系统中各个节点时钟的不同步现象。这种不同步可能会影响到分布式系统的一致性和正确性…...
VMware vCenter 从6.7跨版本升级至7.0U3N
本文尝试使用 vCenter Server Appliance 管理界面 (VAMI) 进行对vCenter Server Appliance7应用进行小版本升级,从6.7.0.47000升级到7.0.3.01600(7.0U3N)。 一、升级前的准备工作 1、检查当前运行环境(当前为6.7.0.47000&#x…...
大麦订单生成器最新版 大麦订单一键生成截图
1.可以一键添加,生成的假订单没有水印,界面也很真实。 2.在软件中输入生成的信息,这是产品信息,选择生成的产品图像,最后生成它。 后台一键生成,独立后台管理 教程:解压源码,修改数…...
如何对Map集合的key进行大小写转换?
工具类: 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
发现一个现象,就是项目中有一个类,如果将函数实现全部放到头文件中,编译不报错,如果将函数实现放到CPP中则始终提示“无法解析的外部符号...”,考虑到放到头文件中能正常编译运行,显然这里不符合“无法解析…...
异步FIFO设计的仿真与综合技术(3)
概述 本文主体翻译自C. E. Cummings and S. Design, “Simulation and Synthesis Techniques for Asynchronous FIFO Design 一文,添加了笔者的个人理解与注释,文中蓝色部分为笔者注或意译。前文链接: 异步FIFO设计的仿真与综合技术…...
什么是区块链,解释区块链的原理和应用场景
1、什么是区块链,解释区块链的原理和应用场景。 区块链是一种分布式数据库,它由一系列按照时间顺序排列的数据块组成,并采用密码学方式保证不可篡改和不可伪造。区块链技术最初起源于比特币,作为比特币的底层技术,用于…...
使用bert进行文本二分类
构建BERT(Bidirectional Encoder Representations from Transformers)的训练网络可以使用PyTorch来实现。下面是一个简单的示例代码: import torch import torch.nn as nn from transformers import BertModel, BertTokenizer# Load BERT to…...
用Windows Installer CleanUp Utility 在windows server上面将软件卸载干净,比如SQLSERVER
这里写自定义目录标题 下载文件: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)---逻辑回归(含手写公式、推导过程和手写例题)
逻辑回归 一、逻辑回归概述二、模型、策略和优化(手写)三、w和b的梯度下降公式推导四、例题分析4.1 题目4.2 解答 一、逻辑回归概述 1. 逻辑回归也称作logistic回归分析,是一种广义的线性回归分析模型,属于机器学习中的监督学习。…...
LLFormer 论文阅读笔记
Ultra-High-Definition Low-Light Image Enhancement: A Benchmark and Transformer-Based Method 这是南京大学在AAAI 2023发表的一篇AAAI2023 超高清图像暗图增强的工作。提出了一个超高清暗图增强数据集,提供了4K和8K的图片,同时提出了一个可用于暗图…...
JSP语法基础习题
目录 简答题:jsp中静态include和动态include的区别是什么? 简答题:jsp有哪些内置对象,作用分别是什么? 简答题:Request对象的主要方法有哪些? 代码题: 简答题: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,check-change 事件编辑进来,父级的半选状态处理 总结 前言 在开发后台管理系统的时候,用户的权限控制是一个常见的需求。这里…...
js中事件委托和事件绑定之间的区别
聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 事件绑定(Event Binding)⭐事件委托(Event Delegation)⭐ 选择事件绑定或事件委托⭐ 写在最后 ⭐ 专栏简介 前端入门之旅:探索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传输文件功能的…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
