可达路径
文章讲解/视频讲解
【题目描述】
给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个程序，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。
【输入描述】
第一行包含两个整数 N，M，表示图中拥有 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 <= 100
- 1 <= 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) } })()
