All Paths From Source to Target
给一个DAG(有向无圈图), 求从0到n-1的所有路径.
直接dfs
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public: vector<vector<int>> res; vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { vector<int> tmp; dfs(graph, tmp, 0); return res; } void dfs(vector<vector<int>>& graph, vector<int>& tmp, int cur){ tmp.push_back(cur); if(cur == graph.size() - 1){ res.push_back(tmp); return; } for(auto i : graph[cur]){ dfs(graph, tmp, i); tmp.pop_back(); } } }; |