Advertisement
SalmaYasser

All Paths From Source to Target

Dec 18th, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. void dfs (vector<vector<int>>& graph, vector <int> &path , vector < vector <int> > &res, int src , int dis, vector <bool> &vis )
  2. {
  3. path.push_back (src);
  4.  
  5. if (src == dis)
  6. {
  7. res.push_back (path);
  8. return;
  9. }
  10.  
  11. for (int i = 0 ; i < graph[src].size(); i++ )
  12. {
  13. int cur = graph[src][i];
  14.  
  15. if (!vis[cur])
  16. {
  17. vis [cur] = true;
  18. dfs (graph, path, res, cur, dis, vis);
  19. if (path.size())
  20. path.pop_back();
  21. vis[cur] = false;
  22.  
  23. }
  24.  
  25. }
  26. }
  27. vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
  28.  
  29. vector < vector <int> > res;
  30. vector <int> path;
  31. vector <bool> vis (graph.size(), false);
  32. dfs (graph , path, res, 0 , graph.size() - 1, vis );
  33.  
  34. return res;
  35.  
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement