aboutsummaryrefslogtreecommitdiff
path: root/check_existence_edge.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /check_existence_edge.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'check_existence_edge.c')
-rw-r--r--check_existence_edge.c66
1 files changed, 66 insertions, 0 deletions
diff --git a/check_existence_edge.c b/check_existence_edge.c
new file mode 100644
index 0000000..2a70cc4
--- /dev/null
+++ b/check_existence_edge.c
@@ -0,0 +1,66 @@
+// 1697. Checking Existence of Edge Length Limited Paths
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * an undirected graph of 'n' nodes is defined by 'edge_list',
+ * where 'edge_list[i] = [ui, vi, disi]' denotes an edge between
+ * nodes 'ui' and 'vi' with distance 'disi'. note that there may
+ * be multiple edges between two nodes. given an array 'queries',
+ * where 'queries[j] = [pj, qj, limitj]', your task is to determine
+ * for each 'queries[j]' whthere there is a path between 'pj' and
+ * 'qj' such that each edge on the path has a distance strictly less
+ * than 'limitj'. return boolean array where 'ans.length == queries.len'
+ * and the j'th value of 'ans' is true if there is a path for
+ * 'queries[j]' is true, and false otherwise
+ */
+
+int *root, **qcopy;
+
+int find(int x) {
+ if (x == root[x])
+ return x;
+ else
+ return root[x] = find(root[x]);
+}
+
+int cmp(void const *a, void const *b) {
+ return (*(int **)a)[2] - (*(int **)b)[2];
+}
+
+int cmp2(void const *a, void const *b) {
+ return qcopy[*(int *)a][2] - qcopy[*(int *)b][2];
+}
+
+bool *distanceLimitedPathsExist(int n, int **edge_list, int edge_list_size,
+ int *edge_list_col_size, int **queries,
+ int queries_size, int *queries_col_size,
+ int *return_size) {
+ *return_size = queries_size;
+ int i = 0;
+ root = (int *)malloc(sizeof(int) * n);
+ for (i = 0; i < n; i++)
+ root[i] = i;
+ bool *ans = (bool *)malloc(sizeof(bool) * queries_size);
+ int idx[queries_size];
+ for (i = 0; i < queries_size; ++i)
+ idx[i] = i;
+ qcopy = queries;
+ qsort(idx, queries_size, sizeof(int), cmp2);
+ qsort(edge_list, edge_list_size, sizeof(int *), cmp);
+ int j = 0;
+ for (i = 0; i < queries_size; ++i) {
+ int curr = idx[i], len = queries[curr][2];
+ while (j < edge_list_size && edge_list[j][2] < len) {
+ int a = find(edge_list[j][0]), b = find(edge_list[j][1]);
+ root[b] = a;
+ j++;
+ }
+ if (find(queries[curr][0]) == find(queries[curr][1]))
+ ans[curr] = 1;
+ else
+ ans[curr] = 0;
+ }
+ return ans;
+}