aboutsummaryrefslogtreecommitdiff
path: root/eventual_safe_states.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'eventual_safe_states.cpp')
-rw-r--r--eventual_safe_states.cpp47
1 files changed, 22 insertions, 25 deletions
diff --git a/eventual_safe_states.cpp b/eventual_safe_states.cpp
index 659115b..2a79b77 100644
--- a/eventual_safe_states.cpp
+++ b/eventual_safe_states.cpp
@@ -13,33 +13,30 @@
*/
class Solution {
- unordered_set<int> cycle_nodes, safe_nodes;
- bool dfs(const vvd(int) & graph, int i, unordered_set<int> visited) {
- if (safe_nodes.find(i) != safe_nodes.end())
- return true;
- if (cycle_nodes.find(i) != cycle_nodes.end())
- return false;
- if (visited.find(i) != visited.end()) {
- cycle_nodes.insert(i);
- return false;
- }
- visited.insert(i);
- for (int node : graph[i])
- if (!dfs(graph, node, visited)) {
- cycle_nodes.insert(i);
- return false;
- }
- safe_nodes.insert(i);
- return true;
- }
-
public:
- vector<int> eventualSafeNodes(vvd(int) & graph) {
+ vector<int> eventualSafeNodes(vector<vector<int>> &graph) {
+ int n = graph.size();
+ vector<vector<int>> g(n);
+ vector<int> dp(n, 0);
+ for (int i = 0; i < n; i++)
+ for (int j = 0; j < graph[i].size(); j++) {
+ g[graph[i][j]].push_back(i);
+ dp[i]++;
+ }
+ queue<int> q;
+ for (int i = 0; i < n; i++)
+ if (!dp[i])
+ q.push(i);
vector<int> ans;
- unordered_set<int> visited;
- for (int i = 0; i < graph.size(); i++)
- if (dfs(graph, i, visited))
- ans.push_back(i);
+ while (!q.empty()) {
+ int u = q.front();
+ q.pop();
+ ans.push_back(u);
+ for (int v : g[u])
+ if (!--dp[v])
+ q.push(v);
+ }
+ sort(ans.begin(), ans.end());
return ans;
}
};