leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0802.cpp (2112B)

0 class Solution { 1 public: 2 vector<int> eventualSafeNodes(const vector<vector<int>> &graph) { 3 int n = graph.size(); 4 vector<bool> visited(n, false), safe(n, false); 5 stack<int> st; 6 for (int i = 0; i < n; i++) { 7 if (visited[i]) continue; 8 st.push(i); 9 while (!st.empty()) { 10 int root = st.top(); 11 if (root == -1) { 12 st.pop(); 13 root = st.top(); 14 st.pop(); 15 bool s = true; 16 for (int c : graph[root]) 17 if (!safe[c]) { 18 s = false; 19 break; 20 } 21 safe[root] = s; 22 continue; 23 } 24 if (visited[root]) { 25 st.pop(); 26 continue; 27 }; 28 visited[root] = true; 29 st.push(-1); 30 for (int c : graph[root]) 31 if (!visited[c]) st.push(c); 32 } 33 } 34 vector<int> res; 35 for (int i = 0; i < n; i++) 36 if (safe[i]) res.push_back(i); 37 return res; 38 } 39 }; 40 41 // Cleaner code, more memory 42 class Solution { 43 int safe[100001] = {0}, count[10001] = {0}; 44 45 public: 46 vector<int> eventualSafeNodes(const vector<vector<int>> &graph) { 47 int n = graph.size(); 48 vector<vector<int>> adj(n); 49 for (int i = 0; i < n; i++) { 50 count[i] += graph[i].size(); 51 for (int node : graph[i]) 52 adj[node].push_back(i); 53 } 54 55 queue<int> q; 56 for (int i = 0; i < n; i++) 57 if (!count[i]) q.push(i); 58 59 while (!q.empty()) { 60 int root = q.front(); 61 q.pop(); 62 safe[root] = true; 63 64 for (auto node : adj[root]) 65 if (!--count[node]) q.push(node); 66 } 67 68 vector<int> res; 69 for (int i = 0; i < graph.size(); i++) 70 if (safe[i]) res.push_back(i); 71 return res; 72 } 73 };