企业官网建设流程全解析

网站主色调有几种,医药公司网站建设方案,公司简介海报,wordpress防盗图可达路径 文章讲解/视频讲解 【题目描述】 给定一个有 n 个节点的有向无环图#xff0c;节点编号从 1 到 n。请编写一个程序#xff0c;找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。 【输入描述】 第一行包含两个整数 N#xff0c;M…可达路径文章讲解/视频讲解【题目描述】给定一个有 n 个节点的有向无环图节点编号从 1 到 n。请编写一个程序找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。【输入描述】第一行包含两个整数 NM表示图中拥有 N 个节点M 条边后续 M 行每行包含两个整数 s 和 t表示图中的 s 节点与 t 节点中有一条路径【输出描述】输出所有的可达路径路径中所有节点的后面跟一个空格每条路径独占一行存在多条路径路径输出的顺序可任意。如果不存在任何一条路径则输出 -1。注意输出的序列中最后一个节点后面没有空格 例如正确的答案是1 3 5,而不是1 3 5 5后面没有空格【输入示例】5 5 1 3 3 5 1 2 2 4 4 5【输出示例】1 3 5 1 2 4 5提示信息用例解释有五个节点其中的从 1 到达 5 的路径有两个分别是 1 - 3 - 5 和 1 - 2 - 4 - 5。因为拥有多条路径所以输出结果为1 3 5 1 2 4 5或1 2 4 5 1 3 5都算正确。数据范围图中不存在自环图中不存在平行边1 N 1001 M 500思路今天正式开始图论章节的更新这段时间的所有题目都来源于卡码网这是为了练习acm输入方式没错图论的所有题都将会是以acm输入输出方式编写因为图的输入和输出在面试中是非常重要的环节习惯了力扣的核心代码输出方式面试官让你手撕就傻了眼了。本题我们用的是dfs深度有优先搜索要使用深搜三部曲其实就类似之前二叉树章节使用过的递归三部曲和回溯章节的回溯三部曲。我们先来看图的存储有两种存储方式可选邻接表和邻接矩阵本题我们就用邻接矩阵来存储这个图。邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图有多少节点就申请多大的二维数组。本题我们会有n 个节点因为节点标号是从1开始的为了节点标号和下标对齐我们申请 n 1 * n 1 这么大的二维数组。然后再输入m个边构造方式如下while (M--) { line await readline() if (line) { [from, to] line.split( ).map(i parseInt(i)) graph[from][to] 1 } }然后就可以开始写深搜三部曲了1.确定递归函数及其传入参数一共需要传入三个参数需要搜索的图表当前遍历的值x遍历的重点n。2.确定终止条件如果我们在遍历的过程中x n了说明找到了一条结果我们就要把当前路径存入结果数组中并且返回。3.处理目前搜索节点出发的路径首先是要找到 x节点指向了哪些节点呢 遍历方式是这样的for (let i 1; i n; i) { if (graph[x][i] 1) {这里我们的graph数组的值为1说明可以到达接下来就是将 选中的x所指向的节点加入到 单一路径来。path.push(i)进入下一层递归dfs(graph, i, n); // 进入下一层递归最后就是回溯的过程撤销本次添加节点的操作。回溯这一步不必多说之前一整个回溯章节都在使用。最后打印结果的时候也要注意不能出错acm模式麻烦就麻烦在这里注意每一个结果的最后一个数字是有不能空格的虽然看不见好像也不影响最终结果但是你多了个空格就是不给你过1 3 5而不是1 3 5即 5 的后面没有空格代码示例const r1 require(readline).createInterface({ input: process.stdin }); // 创建readline接口 let iter r1[Symbol.asyncIterator](); // 创建异步迭代器 const readline async ()(await iter.next()).value; let graph let N, M let result [] let path [] async function initGraph() { let line; line await readline(); [N, M] line.split( ).map(i parseInt(i)) graph new Array(N 1).fill(0).map(() new Array(N 1).fill(0)) while (M--) { line await readline() if (line) { [from, to] line.split( ).map(i parseInt(i)) graph[from][to] 1 } } } function dfs(graph, x, n) { if (x n) { result.push([...path]) return } for (let i 1; i n; i) { if (graph[x][i] 1) { path.push(i) dfs(graph, i, n) path.pop() } } } (async function () { await initGraph() path.push(1) dfs(graph, 1, N) if (result.length 0) { result.forEach(i { console.log(i.join( )) }) } else { console.log(-1) } })()