aboutsummaryrefslogtreecommitdiff
path: root/remove_max_edge.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'remove_max_edge.cpp')
-rw-r--r--remove_max_edge.cpp58
1 files changed, 58 insertions, 0 deletions
diff --git a/remove_max_edge.cpp b/remove_max_edge.cpp
new file mode 100644
index 0000000..fb73f0b
--- /dev/null
+++ b/remove_max_edge.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<int> &ds, int i) {
+ return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]);
+ }
+ int maxNumEdgesToRemove(int n, vvd(int) & edges) {
+ vector<int> 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));
+}