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 };