leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0797.cpp (915B)


      1 class Solution {
      2   public:
      3     vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
      4         int n = graph.size();
      5 
      6         vector<vector<int>> res;
      7         unordered_set<int> visited;
      8         vector<int> path;
      9         stack<int> st;
     10 
     11         st.push(0);
     12         while (!st.empty()) {
     13             int root = st.top();
     14             st.pop();
     15 
     16             if (root == n - 1) {
     17                 path.push_back(root);
     18                 res.push_back(path);
     19                 path.pop_back();
     20                 continue;
     21             }
     22 
     23             if (visited.count(root)) {
     24                 visited.erase(root);
     25                 path.pop_back();
     26                 continue;
     27             }
     28 
     29             path.push_back(root);
     30             visited.insert(root);
     31             st.push(root);
     32 
     33             for (int n : graph[root])
     34                 if (!visited.count(n)) st.push(n);
     35         }
     36 
     37         return res;
     38     }
     39 };