今日份題目：

給你一個有 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;}
};

提交結果

?歡迎大家在評論區討論，如有不懂的代碼部分，歡迎在評論區留言！