难度 中等
题目 Leetcode:
All Paths From Source to Target
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.
The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).
题目解析
本题用到了很基础的dfs，可以说是模板题了。
所以具体的直接看代码的注释吧
1 class Solution { 2 public: 3 vector<vector<int>> ans; 4 vector<int> temp; 5 void dfs(vector<vector<int>>& a, int x, int n) 6 { 7 if (x == n) //如果当前节点到达目标节点，那么把当前路径记录到ans容器种并返回 8 { 9 ans.push_back(temp); 10 return; 11 } 12 for (auto& y : a[x]) //遍历当前节点的目的地 13 { 14 temp.push_back(y); 15 dfs(a, y, n); 16 temp.pop_back(); 17 } 18 } 19 vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { 20 temp.push_back(0);//从0开始 21 int des=graph.size()-1; 22 dfs(graph, 0,des);//数组 当前节点 目标节点 23 return ans; 24 } 25 };