797. All Paths From Source to Target

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void traverse(vector<vector<int>>& graph, int cur, vector<int>& path, vector<vector<int>>& ret){
        // 添加節點至路徑
        path.push_back(cur);
        if(path.back() == graph.size()-1){
            // 抵達終點
            ret.push_back(path);
            path.pop_back();
            return;
        }
        // 遞迴每個相鄰節點
        for(int  neighbor:graph[cur]){
            traverse(graph, neighbor, path, ret);
            
        }
        
        path.pop_back();
        
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        
        vector<vector<int>> ret;
        vector<int> path;
        traverse(graph, 0, path, ret);
        return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> ret;
    void dfs(vector<vector<int>> &graph, vector<int> &path, int start){
        
        path.push_back(start);
        if(!path.empty() && path.back() == graph.size()-1){
            ret.push_back(path);
        }
        for(auto a:graph[start]){
            dfs(graph, path, a);
        }
        path.pop_back();
    }
    
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> path;
        dfs(graph, path, 0);
        return ret;
        
    }
};

analysis

  • time complexity O(V+E)
  • space complexity O(V)