leetcode

commit 152e80a8f793e797fe3edda9f4f7881d868c455b
parent f96db6a17ac23cf68683f19555c814040a19349f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 12 Jul 2023 22:20:12 +0200

Improved Daily Problem

Diffstat:
M
Problems/0802.cpp
 | 
48
+++++++++++++++++++++++++++++++++++++++++-------

1 file changed, 41 insertions(+), 7 deletions(-)
diff --git a/Problems/0802.cpp b/Problems/0802.cpp
@@ -1,18 +1,16 @@
 class Solution {
 public:
-  vector<int> eventualSafeNodes(vector<vector<int>> &graph) {
+  vector<int> eventualSafeNodes(const vector<vector<int>> &graph) {
     int n = graph.size();
-    vector<int> res;
-    vector<bool> visited(n, false);
-    vector<bool> safe(n, false);
+    vector<bool> visited(n, false), safe(n, false);
     stack<int> st;
     for (int i = 0; i < n; i++) {
       if (visited[i]) continue;
       st.push(i);
       while (!st.empty()) {
         int root = st.top();
-        st.pop();
         if (root == -1) {
+          st.pop();
           root = st.top();
           st.pop();
           bool s = true;
@@ -24,16 +22,52 @@ public:
           safe[root] = s;
           continue;
         }
-        if (visited[root]) continue;
+        if (visited[root]) {
+          st.pop();
+          continue;
+        };
         visited[root] = true;
-        st.push(root);
         st.push(-1);
         for (int c : graph[root])
           if (!visited[c]) st.push(c);
       }
     }
+    vector<int> res;
     for (int i = 0; i < n; i++)
       if (safe[i]) res.push_back(i);
     return res;
   }
 };
+
+// Cleaner code, more memory
+class Solution {
+  int safe[100001] = {0}, count[10001] = {0};
+
+public:
+  vector<int> eventualSafeNodes(const vector<vector<int>> &graph) {
+    int n = graph.size();
+    vector<vector<int>> adj(n);
+    for (int i = 0; i < n; i++) {
+      count[i] += graph[i].size();
+      for (int node : graph[i]) adj[node].push_back(i);
+    }
+
+    queue<int> q;
+    for (int i = 0; i < n; i++)
+      if (!count[i]) q.push(i);
+
+    while (!q.empty()) {
+      int root = q.front();
+      q.pop();
+      safe[root] = true;
+
+      for (auto node : adj[root])
+        if (!--count[node]) q.push(node);
+    }
+
+    vector<int> res;
+    for (int i = 0; i < graph.size(); i++)
+      if (safe[i]) res.push_back(i);
+    return res;
+  }
+};