aboutsummaryrefslogtreecommitdiff
path: root/all_path_src_target.cpp
blob: ae261aad51dd8fca7f155ec9a2e82892adf39bb9 (plain)
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
30
#include "leetcode.h"

class Solution {
public:
  vvd(int) allPathsSourceTarget(vvd(int) & graph) {
    vvd(int) ans;
    vector<int> path;
    dfs(graph, ans, path, 0);
    return ans;
  }

private:
  void dfs(vvd(int) & graph, vvd(int) & ans, vector<int> &path, int curr) {
    path.push_back(curr);
    if (curr == graph.size() - 1)
      ans.push_back(path);
    else
      for (auto it : graph[curr])
        dfs(graph, ans, path, it);
    path.pop_back();
  }
};

int main() {
  Solution obj;
  vvd(int) graph = {{1, 2}, {3}, {3}, {}};
  for (auto i : obj.allPathsSourceTarget(graph))
    for (auto j : i)
      cout << j << ' ';
}