题目链接:https://leetcode-cn.com/problems/all-paths-from-source-to-target
题目描述:
给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)
二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点,空就是没有下一个结点了。
译者注:有向图是有方向的,即规定了 a→b 你就不能从 b→a 。
题解:
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<int> path(1, 0);
trackingBack(0, graph.size(), graph, path);
return ans;
}
void trackingBack(int cur, int n, vector<vector<int>>& graph, vector<int> &curpath)
{
if(cur == n - 1)
{
ans.push_back(curpath);
return;
}
for(auto node: graph[cur])
{
curpath.push_back(node);
trackingBack(node, n, graph, curpath);
curpath.pop_back();
}
}
};