aboutsummaryrefslogtreecommitdiff
path: root/redundant_connection.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-29 10:14:56 -0700
committerJack Sangdahl <[email protected]>2025-01-29 10:14:56 -0700
commitc6b14242923a5f02b2d2f29457e11f4b7b393d77 (patch)
tree35fe54b3d9a47f8909165bb2f9e1601311d4f478 /redundant_connection.c
parent11539b9148c40d75105e056f31a152f70433d640 (diff)
downloadleetcode-c6b14242923a5f02b2d2f29457e11f4b7b393d77.tar.gz
leetcode-c6b14242923a5f02b2d2f29457e11f4b7b393d77.zip
684. redundant connection
Diffstat (limited to 'redundant_connection.c')
-rw-r--r--redundant_connection.c72
1 files changed, 72 insertions, 0 deletions
diff --git a/redundant_connection.c b/redundant_connection.c
new file mode 100644
index 0000000..43036d1
--- /dev/null
+++ b/redundant_connection.c
@@ -0,0 +1,72 @@
+// 684. Redundant Connection
+#include "leetcode.h"
+
+/*
+ * in this problem, a tree is an undirected graph that is connected and has no
+ * cycles. you are given a graph that started as a tree with 'n' nodes labeled
+ * from 1 to 'n', with one additional edge added. the added edge has two
+ * different vertices chosen from 1 to 'n', and was not an edge that already
+ * existed. the graph is represented as an array 'edges' of length 'n' where
+ * 'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
+ * and 'b_i' in the graph. return an edge that can removed so that the resulting
+ * graph is a tree of 'n' nodes. if there are multiple answers, return the
+ * answer that occurs last in the input.
+ */
+
+int find(int *parent, int x) {
+ if (parent[x] != x)
+ parent[x] = find(parent, parent[x]);
+ return parent[x];
+}
+
+void union_set(int *parent, int *rank, int x, int y) {
+ int root_x = find(parent, x), root_y = find(parent, y);
+ if (root_x != root_y) {
+ if (rank[root_x] > rank[root_y])
+ parent[root_y] = root_x;
+ else if (rank[root_x] < rank[root_y])
+ parent[root_x] = root_y;
+ else {
+ parent[root_y] = root_x;
+ rank[root_x]++;
+ }
+ }
+}
+
+int *findRedundantConnection(int **edges, int edgesSize, int *edgesColSize,
+ int *returnSize) {
+ int *parent = (int *)malloc((edgesSize + 1) * sizeof(int));
+ int *rank = (int *)calloc(edgesSize + 1, sizeof(int));
+ int *result = (int *)malloc(2 * sizeof(int));
+ *returnSize = 2;
+ for (int i = 1; i <= edgesSize; i++)
+ parent[i] = i;
+ for (int i = 0; i < edgesSize; i++) {
+ int u = edges[i][0], v = edges[i][1];
+ if (find(parent, u) == find(parent, v)) {
+ result[0] = u;
+ result[1] = v;
+ } else
+ union_set(parent, rank, u, v);
+ }
+ free(parent), free(rank);
+ return result;
+}
+
+int main() {
+ int e1i[3][2] = {{1, 2}, {1, 3}, {2, 3}}, rs1;
+ int e2i[5][2] = {{1, 2}, {2, 3}, {3, 4}, {1, 4}, {1, 5}}, rs2;
+ struct two_d_arr e1, e2;
+ two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i);
+ two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i);
+ int *frc1 = findRedundantConnection(e1.arr, e1.row_size, e1.col_size, &rs1);
+ int *frc2 = findRedundantConnection(e2.arr, e2.row_size, e2.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", frc1[i]); // expect: 2 3
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", frc2[i]); // expect: 1 4
+ printf("\n");
+ free(frc1), two_d_arr_free(&e1);
+ free(frc2), two_d_arr_free(&e2);
+}