From 0cea53b366c1ef1b94693772b8f3c3299fcd699b Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Sat, 29 Jun 2024 18:33:35 -0600 Subject: 1579. remove max number edges graph --- remove_max_edge.cpp | 58 ------------------------------ remove_max_num_edge_traverse.c | 76 ++++++++++++++++++++++++++++++++++++++++ remove_max_num_edge_traverse.cpp | 58 ++++++++++++++++++++++++++++++ remove_max_num_edge_traverse.py | 73 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 207 insertions(+), 58 deletions(-) delete mode 100644 remove_max_edge.cpp create mode 100644 remove_max_num_edge_traverse.c create mode 100644 remove_max_num_edge_traverse.cpp create mode 100644 remove_max_num_edge_traverse.py diff --git a/remove_max_edge.cpp b/remove_max_edge.cpp deleted file mode 100644 index fb73f0b..0000000 --- a/remove_max_edge.cpp +++ /dev/null @@ -1,58 +0,0 @@ -// 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 - */ - -class Solution { -public: - int find(vector &ds, int i) { - return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]); - } - int maxNumEdgesToRemove(int n, vvd(int) & edges) { - vector ds_both(n + 1, -1); - int used = 0; - for (int type = 3; type > 0; --type) { - auto ds_one = ds_both; - auto &ds = type == 3 ? ds_both : ds_one; - for (auto &e : edges) { - if (e[0] == type) { - int i = find(ds, e[1]), j = find(ds, e[2]); - if (i != j) { - ++used; - if (ds[j] < ds[i]) - swap(i, j); - ds[i] += ds[j]; - ds[j] = i; - } - } - } - if (type != 3 && ds[find(ds, 1)] != -n) - return -1; - } - return edges.size() - used; - } -}; - -int main() { - Solution obj; - vvd(int) - e1 = {{3, 1, 2}, {3, 2, 3}, {1, 1, 3}, {1, 2, 4}, {1, 1, 2}, {2, 3, 4}}; - vvd(int) e2 = {{3, 1, 2}, {3, 2, 3}, {1, 1, 4}, {2, 1, 4}}; - vvd(int) e3 = {{3, 2, 3}, {1, 1, 2}, {2, 3, 4}}; - printf("%d\n", obj.maxNumEdgesToRemove(4, e1)); - printf("%d\n", obj.maxNumEdgesToRemove(4, e2)); - printf("%d\n", obj.maxNumEdgesToRemove(4, e3)); -} 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_num_edge_traverse.cpp b/remove_max_num_edge_traverse.cpp new file mode 100644 index 0000000..fb73f0b --- /dev/null +++ b/remove_max_num_edge_traverse.cpp @@ -0,0 +1,58 @@ +// 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 + */ + +class Solution { +public: + int find(vector &ds, int i) { + return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]); + } + int maxNumEdgesToRemove(int n, vvd(int) & edges) { + vector ds_both(n + 1, -1); + int used = 0; + for (int type = 3; type > 0; --type) { + auto ds_one = ds_both; + auto &ds = type == 3 ? ds_both : ds_one; + for (auto &e : edges) { + if (e[0] == type) { + int i = find(ds, e[1]), j = find(ds, e[2]); + if (i != j) { + ++used; + if (ds[j] < ds[i]) + swap(i, j); + ds[i] += ds[j]; + ds[j] = i; + } + } + } + if (type != 3 && ds[find(ds, 1)] != -n) + return -1; + } + return edges.size() - used; + } +}; + +int main() { + Solution obj; + vvd(int) + e1 = {{3, 1, 2}, {3, 2, 3}, {1, 1, 3}, {1, 2, 4}, {1, 1, 2}, {2, 3, 4}}; + vvd(int) e2 = {{3, 1, 2}, {3, 2, 3}, {1, 1, 4}, {2, 1, 4}}; + vvd(int) e3 = {{3, 2, 3}, {1, 1, 2}, {2, 3, 4}}; + printf("%d\n", obj.maxNumEdgesToRemove(4, e1)); + printf("%d\n", obj.maxNumEdgesToRemove(4, e2)); + printf("%d\n", obj.maxNumEdgesToRemove(4, e3)); +} 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]])) -- cgit v1.2.3