C++刷LeetCode（797. 所有可能的路径）【回溯】

糖逗

题目描述：

1. 给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）
   
2. 
   
3. 二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了a→b你就不能从b→a）空就是没有下一个结点了。
   
4. 
   
5. 示例:
   
6. 输入: [[1,2], [3], [3], []]
   
7. 输出: [[0,1,3],[0,2,3]]
   
8. 解释: 图是这样的:
   
9. 0--->1
   
10. |    |
    
11. v    v
    
12. 2--->3
    
13. 这有两条路: 0 -> 1 -> 3 和 0 -> 2 -> 3.
    
14. 提示:
    
15. 
    
16. 结点的数量会在范围 [2, 15] 内。
    
17. 你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。

复制代码

1. class Solution {
   
2. public:
   
3.     void dfs(vector<vector<int> > &graph, vector<int>&temp, vector<vector<int> > & res, int cur, vector<int>&visit){
   
4.         if(graph[cur].size() == 0){
   
5.             if(cur == graph.size() - 1) res.push_back(temp);
   
6.             return;
   
7.         }
   
8.         if(cur == graph.size() - 1)res.push_back(temp);
   
9.         int len = graph[cur].size();
   
10.         for(int i = 0; i < len; i++){
    
11.             int number = graph[cur][i];
    
12.             if(visit[number] == 0){
    
13.                 int node = number;
    
14.                 visit[node] = 1;
    
15.                 temp.push_back(node);
    
16.                 dfs(graph, temp, res, node, visit);
    
17.                 temp.pop_back();
    
18.                 visit[node] = 0;
    
19.             }
    
20.         }
    
21.     }
    
22.     vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    
23.         //深度优先搜索+回溯
    
24.         vector<vector<int> > res;
    
25.         vector<int> temp;
    
26.         temp.push_back(0);
    
27.         int len = graph.size();
    
28.         vector<int> visit(len, 0);
    
29.         visit[0] = 1;
    
30.         dfs(graph, temp, res, 0, visit);
    
31.         return res;
    
32.     }
    
33. };

复制代码