aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-06-29 18:33:35 -0600
committerJack Sangdahl <[email protected]>2024-06-29 18:33:35 -0600
commit0cea53b366c1ef1b94693772b8f3c3299fcd699b (patch)
tree07af9d255265eee3845554934147a2fdf51a9ce7
parent31c33591e4be1cc400e4de23b7fe097c7513e35c (diff)
downloadleetcode-0cea53b366c1ef1b94693772b8f3c3299fcd699b.tar.gz
leetcode-0cea53b366c1ef1b94693772b8f3c3299fcd699b.zip
1579. remove max number edges graph
-rw-r--r--remove_max_num_edge_traverse.c76
-rw-r--r--remove_max_num_edge_traverse.cpp (renamed from remove_max_edge.cpp)0
-rw-r--r--remove_max_num_edge_traverse.py73
3 files changed, 149 insertions, 0 deletions
diff --git a/remove_max_num_edge_traverse.c b/remove_max_num_edge_traverse.c
new file mode 100644
index 0000000..3dda41a
--- /dev/null
+++ b/remove_max_num_edge_traverse.c
@@ -0,0 +1,76 @@
+// 1579. Remove Max Number of Edges to Keep Graph Fully Traversable
+#include "leetcode.h"
+
+/*
+ * alice and bob have an undirected graph of 'n' nodes and three
+ * types of edges:
+ * type1: can be traversed by alice only
+ * type2: can be traversed by bob only
+ * type3: can be traversed by both alice and bob
+ * given an array of 'edges' where 'edges{i} = {typei, ui, vi}'
+ * represents a bidirectional edge of type 'typei' between nodes
+ * 'ui' and 'vi', find the maximum number of edges you can remove
+ * so that after removing the edges, the graph can still be fully
+ * traversed by alice and bob if starting from any node, they can
+ * reach all other nodes. return the maximum number of edges you
+ * can remove, or return -1 if alice and bob cannot traverse graph
+ */
+
+int find(int *n, int target) {
+ return n[target] < 0 ? target : (n[target] = find(n, n[target]));
+}
+
+int connect(int *n, int x, int y) {
+ int a = find(n, x), b = find(n, y);
+ if (a == b)
+ return 0;
+ if (n[a] > n[b])
+ n[a] = b;
+ else if (n[b] > n[a])
+ n[b] = a;
+ else {
+ n[a] = b;
+ n[b]--;
+ }
+ return 1;
+}
+
+int maxNumEdgesToRemove(int n, int **edges, int edgesSize, int *edgesColSize) {
+ int e = 0, f = 0, g = 0, b = n, c = n, d = n;
+ int *p = (int *)malloc(n * sizeof(*p));
+ int *q = (int *)malloc(n * sizeof(*q));
+ int *r = (int *)malloc(n * sizeof(*r));
+ for (int i = 0; i < n; ++i)
+ p[i] = q[i] = r[i] = -1;
+ for (int i = 0; i < edgesSize; i++) {
+ int t = edges[i][0], u = edges[i][1] - 1, v = edges[i][2] - 1;
+ if (t != 1) {
+ e++;
+ b -= connect(p, u, v);
+ }
+ if (t != 2) {
+ f++;
+ d -= connect(q, u, v);
+ }
+ if (t == 3) {
+ g++;
+ d -= connect(r, u, v);
+ }
+ }
+ free(p), free(q), free(r);
+ return b > 1 || c > 1 ? -1 : e + f - g + b + c - d - n;
+}
+
+int main() {
+ int e1[6][3] = {{3, 1, 2}, {3, 2, 3}, {1, 1, 3},
+ {1, 2, 4}, {1, 1, 2}, {2, 3, 4}};
+ int e2[4][3] = {{3, 1, 2}, {3, 2, 3}, {1, 1, 4}, {2, 1, 4}};
+ int e3[3][3] = {{3, 2, 3}, {1, 1, 2}, {2, 3, 4}};
+ int ecs1[] = {6, 6, 6}, ecs2[] = {4, 4, 4}, ecs3[] = {3, 3, 3};
+ printf("%d\n", maxNumEdgesToRemove(4, (int **)e1, ARRAY_SIZE(e1),
+ (int *)ARRAY_SIZE(e1[0]))); // expect: 2
+ printf("%d\n", maxNumEdgesToRemove(4, (int **)e2, ARRAY_SIZE(e2),
+ (int *)ARRAY_SIZE(e2[0]))); // expect: 0
+ printf("%d\n", maxNumEdgesToRemove(4, (int **)e3, ARRAY_SIZE(e3),
+ (int *)ARRAY_SIZE(e3[0]))); // expect: -1
+}
diff --git a/remove_max_edge.cpp b/remove_max_num_edge_traverse.cpp
index fb73f0b..fb73f0b 100644
--- a/remove_max_edge.cpp
+++ b/remove_max_num_edge_traverse.cpp
diff --git a/remove_max_num_edge_traverse.py b/remove_max_num_edge_traverse.py
new file mode 100644
index 0000000..3aee386
--- /dev/null
+++ b/remove_max_num_edge_traverse.py
@@ -0,0 +1,73 @@
+# 1579. Remove Max Number of Edges to Keep Graph Fully Traversable
+
+"""
+alice and bob have an undirected graph of 'n' nodes and three
+types of edges:
+type1: can be traversed by alice only
+type2: can be traversed by bob only
+type3: can be traversed by both alice and bob
+given an array of 'edges' where 'edges{i} = {typei, ui, vi}'
+repansents a bidirectional edge of type 'typei' between nodes
+'ui' and 'vi', find the maximum number of edges you can remove
+so that after removing the edges, the graph can still be fully
+traversed by alice and bob if starting from any node, they can
+reach all other nodes. return the maximum number of edges you
+can remove, or return -1 if alice and bob cannot traverse graph
+"""
+
+
+class Solution(object):
+ def maxNumEdgesToRemove(self, n, edges):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :rtype: int
+ """
+ def find(i):
+ if i != root[i]:
+ root[i] = find(root[i])
+ return root[i]
+ def uni(x, y):
+ x, y = find(x), find(y)
+ if x == y:
+ return 0
+ root[x] = y
+ return 1
+ ans,e1,e2=0,0,0
+ root = range(n + 1)
+ for t, i, j in edges:
+ if t == 3:
+ if uni(i, j):
+ e1 += 1
+ e2 += 1
+ else:
+ ans += 1
+ root0 = root[:]
+ for t, i, j in edges:
+ if t == 1:
+ if uni(i, j):
+ e1 += 1
+ else:
+ ans += 1
+ root = root0
+ for t, i, j in edges:
+ if t == 2:
+ if uni(i, j):
+ e2 += 1
+ else:
+ ans += 1
+ return ans if e1 == e2 == n - 1 else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxNumEdgesToRemove(
+ n=4,
+ edges=[[3, 1, 2], [3, 2, 3], [1, 1, 3], [1, 2, 4], [1, 1, 2], [2, 3, 4]],
+ )
+ )
+ print(
+ obj.maxNumEdgesToRemove(n=4, edges=[[3, 1, 2], [3, 2, 3], [1, 1, 4], [2, 1, 4]])
+ )
+ print(obj.maxNumEdgesToRemove(n=4, edges=[[3, 2, 3], [1, 1, 2], [2, 3, 4]]))