今日份题目:
给你一个有 n
个节点的 有向无环图(DAG),请你找出所有从节点 0
到节点 n-1
的路径并输出(不要求按特定顺序)
graph[i]
是一个从节点 i
可以访问的所有节点的列表(即从节点 i
到节点 graph[i][j]
存在一条有向边)。
示例1
输入:graph = [[1,2],[3],[3],[]] 输出:[[0,1,3],[0,2,3]] 解释:有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例2
输入: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]]
提示
-
n == graph.length
-
2 <= n <= 15
-
0 <= graph[i][j] < n
-
graph[i][j] != i
(即不存在自环) -
graph[i]
中的所有元素 互不相同 -
保证输入为 有向无环图(DAG)
题目思路
使用深度优先遍历,用p数组记录路径。递归遍历结束条件就是到达结尾,所以需要一个int数据记录当前所在位置,如果到结尾了就返回。
代码
class Solution
{
public:
vector<vector<int>> ans;
vector<int> p;
void dfs(vector<vector<int>>& graph, int x, int n)
{ //x用来标记当前所在位置,n标记结尾所在位置
if(x==n) //到结尾了,返回
{
ans.push_back(p);
return;
}
for(auto& y:graph[x]) //遍历临界节点
{
p.push_back(y);
dfs(graph,y,n);
p.pop_back();//还原队列,确保其他dfs操作的正确进行
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph)
{
p.push_back(0);
dfs(graph,0,graph.size()-1);
return ans;
}
};
提交结果
文章来源:https://www.toymoban.com/news/detail-650743.html
欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!文章来源地址https://www.toymoban.com/news/detail-650743.html
到了这里,关于每天一道leetcode:797. 所有可能的路径(图论&中等&深度优先遍历)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!