今日份題目：
給你一個有 n 個節(jié)點的 有向無環(huán)圖（DAG），請你找出所有從節(jié)點 0 到節(jié)點 n-1 的路徑并輸出（不要求按特定順序）
graph[i] 是一個從節(jié)點 i 可以訪問的所有節(jié)點的列表（即從節(jié)點 i 到節(jié)點 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（即不存在自環(huán)） -
graph[i]中的所有元素 互不相同 -
保證輸入為 有向無環(huán)圖（DAG）
題目思路
使用深度優(yōu)先遍歷，用p數(shù)組記錄路徑。遞歸遍歷結(jié)束條件就是到達(dá)結(jié)尾，所以需要一個int數(shù)據(jù)記錄當(dāng)前所在位置，如果到結(jié)尾了就返回。
代碼
class Solution
{
public:
vector<vector<int>> ans;
vector<int> p;
void dfs(vector<vector<int>>& graph, int x, int n)
{ //x用來標(biāo)記當(dāng)前所在位置，n標(biāo)記結(jié)尾所在位置
if(x==n) //到結(jié)尾了，返回
{
ans.push_back(p);
return;
}
for(auto& y:graph[x]) //遍歷臨界節(jié)點
{
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;
}
};
提交結(jié)果
文章來源：http://www.zghlxwxcb.cn/news/detail-650743.html
?歡迎大家在評論區(qū)討論，如有不懂的代碼部分，歡迎在評論區(qū)留言！文章來源地址http://www.zghlxwxcb.cn/news/detail-650743.html
到了這里，關(guān)于每天一道leetcode：797. 所有可能的路徑（圖論&中等&深度優(yōu)先遍歷）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
