C++刷LeetCode（797. 所有可能的路径）【回溯】
题目描述：给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）
二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了a→b你就不能从b→a）空就是没有下一个结点了。
示例:
输入: [, , , []]
输出: [,]
解释: 图是这样的:
0--->1
| |
v v
2--->3
这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3.
提示:
结点的数量会在范围 内。
你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。
class Solution {
public:
void dfs(vector<vector<int> > &graph, vector<int>&temp, vector<vector<int> > & res, int cur, vector<int>&visit){
if(graph.size() == 0){
if(cur == graph.size() - 1) res.push_back(temp);
return;
}
if(cur == graph.size() - 1)res.push_back(temp);
int len = graph.size();
for(int i = 0; i < len; i++){
int number = graph;
if(visit == 0){
int node = number;
visit = 1;
temp.push_back(node);
dfs(graph, temp, res, node, visit);
temp.pop_back();
visit = 0;
}
}
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
//深度优先搜索+回溯
vector<vector<int> > res;
vector<int> temp;
temp.push_back(0);
int len = graph.size();
vector<int> visit(len, 0);
visit = 1;
dfs(graph, temp, res, 0, visit);
return res;
}
};
页:
[1]