aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--eventual_safe_states.c59
-rw-r--r--eventual_safe_states.cpp47
-rw-r--r--eventual_safe_states.py43
3 files changed, 103 insertions, 46 deletions
diff --git a/eventual_safe_states.c b/eventual_safe_states.c
index 21fa5d0..46059a2 100644
--- a/eventual_safe_states.c
+++ b/eventual_safe_states.c
@@ -1,6 +1,5 @@
// 802. Find Eventual Safe States
-#include <stdbool.h>
-#include <stdlib.h>
+#include "leetcode.h"
/*
* there is a directed graph of 'n' nodes with each node labeled from 0 to n
@@ -13,32 +12,50 @@
* should be sorted in ascending order.
*/
-bool dfs(int **graph, int graph_size, int *graph_col_size, int *visited,
- int node) {
- if (visited[node] == 1)
+bool dfs(int **graph, int graphSize, int *graphColSize, int *vis, int node) {
+ if (vis[node] == 1)
return true;
- if (visited[node] == 2)
+ if (vis[node] == 2)
return false;
- visited[node] = 2;
- for (int i = 0; i < graph_col_size[node]; i++)
- if (!dfs(graph, graph_size, graph_col_size, visited, graph[node][i]))
+ vis[node] = 2;
+ for (int i = 0; i < graphColSize[node]; i++)
+ if (!dfs(graph, graphSize, graphColSize, vis, graph[node][i]))
return false;
- visited[node] = 1;
+ vis[node] = 1;
return true;
}
-int *eventualSafeNodes(int **graph, int graph_size, int *graph_col_size,
- int *return_size) {
- int n = graph_size, a_idx = 0;
- int *visited = calloc(n, sizeof(int));
- int *ans = malloc(n * sizeof(int));
+int *eventualSafeNodes(int **graph, int graphSize, int *graphColSize,
+ int *returnSize) {
+ int n = graphSize, idx = 0;
+ int *vis = (int *)calloc(n, sizeof(int));
+ int *ans = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; i++)
- if (dfs(graph, graph_size, graph_col_size, visited, i)) {
- ans[a_idx] = i;
- a_idx++;
+ if (dfs(graph, graphSize, graphColSize, vis, i)) {
+ ans[idx] = i;
+ idx++;
}
- free(visited);
- *return_size = a_idx;
- ans = realloc(ans, a_idx * sizeof(int));
+ free(vis);
+ *returnSize = idx;
+ ans = (int *)realloc(ans, idx * sizeof(int));
return ans;
}
+
+int main() {
+ int g1i[7][2] = {{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}}, rs1;
+ int g2i[5][4] = {{1, 2, 3, 4}, {1, 2}, {3, 4}, {0, 4}, {}}, rs2;
+ struct two_d_arr g1, g2;
+ two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ int *esn1 = eventualSafeNodes(g1.arr, g1.row_size, g1.col_size, &rs1);
+ int *esn2 = eventualSafeNodes(g2.arr, g2.row_size, g2.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", esn1[i]); // expect: 2 4 5 6
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", esn2[i]); // expect: 4
+ printf("\n");
+ free(esn2), free(esn2);
+ two_d_arr_free(&g1);
+ two_d_arr_free(&g2);
+}
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;
}
};
diff --git a/eventual_safe_states.py b/eventual_safe_states.py
new file mode 100644
index 0000000..5d7d79e
--- /dev/null
+++ b/eventual_safe_states.py
@@ -0,0 +1,43 @@
+# 802. Find Eventual Safe States
+from collections import defaultdict
+
+"""
+there is a directed graph of 'n' nodes with each node labeled from 0 to n
+- 1. the graph is represented by a 0-indexed 2d integer array 'graph' where
+'graph[i]' is an integer array of nodes adjacent to node 'i', meaning there
+is an edge from node 'i' to each node in 'graph[i]'. a node is a terminal
+node if there are no outgoing edges. a node is a safe node if every possible
+path starting from that node leads to a terminal node ( or another safe
+node). return an array containing all the safe nodes of the graph. the answer
+should be sorted in ascending order.
+"""
+
+
+class Solution(object):
+ def eventualSafeNodes(self, graph):
+ """
+ :type graph: List[List[int]]
+ :rtype: List[int]
+ """
+ n = len(graph)
+ g = defaultdict(list)
+ dp = [0] * n
+ for i, v in enumerate(graph):
+ dp[i] = len(v)
+ for e in v:
+ g[e].append(i)
+ q = [i for i in range(n) if dp[i] == 0]
+ while q:
+ x = q.pop()
+ for e in g[x]:
+ dp[e] -= 1
+ if dp[e] == 0:
+ q.append(e)
+ ans = [i for i in range(n) if dp[i] == 0]
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.eventualSafeNodes(graph=[[1, 2], [2, 3], [5], [0], [5], [], []]))
+ print(obj.eventualSafeNodes(graph=[[1, 2, 3, 4], [1, 2], [3, 4], [0, 4], []]))