aboutsummaryrefslogtreecommitdiff
path: root/eventual_safe_states.c
diff options
context:
space:
mode:
Diffstat (limited to 'eventual_safe_states.c')
-rw-r--r--eventual_safe_states.c59
1 files changed, 38 insertions, 21 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);
+}