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