797. 所有可能的路径
给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)
二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点,空就是没有下一个结点了。
译者注:有向图是有方向的,即规定了 a→b 你就不能从 b→a 。
输入:graph = [[1,2],[3],[3],[]]
输出:[[0,1,3],[0,2,3]]
解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
输入:graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出:[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
1、python:
from typing import List import json class Solution: def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: ans = list() stk = list() def dfs(x: int): if x == len(graph) - 1: ans.append(stk[:]) return for y in graph[x]: stk.append(y) dfs(y) stk.pop() stk.append(0) dfs(0) return ans if __name__ == ‘__main__‘: graph_input = json.loads(input().strip()) print(Solution().allPathsSourceTarget(graph_input))
2、java:
import com.alibaba.fastjson.JSON; import java.nio.charset.StandardCharsets; import java.util.*; class Solution { List<List<Integer>> ans = new ArrayList<List<Integer>>(); Deque<Integer> stack = new ArrayDeque<Integer>(); public List<List<Integer>> allPathsSourceTarget(int[][] graph) { stack.offerLast(0); dfs(graph, 0, graph.length - 1); return ans; } public void dfs(int[][] graph, int x, int n) { if (x == n) { ans.add(new ArrayList<Integer>(stack)); return; } for (int y : graph[x]) { stack.offerLast(y); dfs(graph, y, n); stack.pollLast(); } } public static void main(String[] args) { Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name()); int[][] graph = JSON.parseObject(cin.nextLine(), int[][].class); System.out.println(new Solution().allPathsSourceTarget(graph)); } }
3、go:
待写
4、c++:
#include "vector" #include "iostream" #include ".\lib\json-3.9.1\single_include\nlohmann\json.hpp" using json = nlohmann::json; using namespace std; class Solution { public: vector<vector<int>> ans; vector<int> stk; void dfs(vector<vector<int>>& graph, int x, int n) { if (x == n) { ans.push_back(stk); return; } for (auto& y : graph[x]) { stk.push_back(y); dfs(graph, y, n); stk.pop_back(); } } vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { stk.push_back(0); dfs(graph, 0, graph.size() - 1); return ans; } }; int main() { string graphInput; getline(cin, graphInput); // nullptr空,就false // 数组字符串转数组 auto graphJson = json::parse(graphInput, nullptr, false); vector<vector<int>> graph = graphJson; auto result = Solution().allPathsSourceTarget(graph); // 数组转数组字符串 auto jsonArray = nlohmann::json::array(); jsonArray = result; auto resultString = jsonArray.dump(); cout << resultString << endl; }
5、javascript:
let allPathsSourceTarget = function(graph) { const stack = [], ans = []; const dfs = (graph, x, n) => { if (x === n) { ans.push(stack.slice()); return; } for (const y of graph[x]) { stack.push(y); dfs(graph, y, n); stack.pop(); } } stack.push(0); dfs(graph, 0, graph.length - 1); return ans; }; let readLine = require("readline"); const rl = readLine.createInterface({ input: process.stdin, output: process.stdout }); rl.on("line", function (line) { let graph = JSON.parse(line); console.log(allPathsSourceTarget(graph)); });
python_java_go_c++_js_输出“[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]”形式的数据