leetcode

commit 11516e28020baf08caeb9f312c286adaf0cfeb68
parent 3fa12cfdd2b561baa15de38dfaed99e72d982c19
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 30 Apr 2023 12:29:14 +0200

Daily Problem

Diffstat:
A
Problems/1579.cpp
 | 
56
++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+
M
Templates/Union_Find.cpp
 | 
3
+++

3 files changed, 60 insertions(+), 0 deletions(-)
diff --git a/Problems/1579.cpp b/Problems/1579.cpp
@@ -0,0 +1,56 @@
+class UnionFind {
+  int n, cnt = n;
+  vector<int> root, size;
+
+public:
+  UnionFind(int n) : n(n), root(n), size(n, 1) {
+    iota(root.begin(), root.end(), 0);
+  }
+
+  UnionFind(const UnionFind &uf)
+      : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {}
+
+  static int redundant;
+
+  int find(int x) {
+    while (x != root[x]) x = root[x] = root[root[x]];
+    return x;
+  }
+
+  void join(int x, int y) {
+    x = find(x), y = find(y);
+    if (x != y) {
+      if (size[x] > size[y]) swap(x, y);
+      root[x] = y;
+      size[y] += size[x];
+      cnt--;
+    } else
+      redundant++;
+  }
+
+  int count() { return cnt; }
+  bool connected(int x, int y) { return find(x) == find(y); }
+};
+
+int UnionFind::redundant = 0;
+
+class Solution {
+public:
+  int maxNumEdgesToRemove(int n, vector<vector<int>> &e) {
+    UnionFind::redundant = 0;
+
+    UnionFind a(n + 1);
+    for (int i = 0; i < e.size(); i++)
+      if (e[i][0] == 3) a.join(e[i][1], e[i][2]);
+
+    UnionFind b = a;
+    for (int i = 0; i < e.size(); i++)
+      if (e[i][0] == 1)
+        a.join(e[i][1], e[i][2]);
+      else if (e[i][0] == 2)
+        b.join(e[i][1], e[i][2]);
+
+    // count must be 2, since 0 is not used
+    return a.count() == 2 && b.count() == 2 ? UnionFind::redundant : -1;
+  }
+};
diff --git a/README.md b/README.md
@@ -455,6 +455,7 @@ for solving problems.
 |  1544  |    Easy    | [Make The String Great](Problems/1544.cpp)                                                       |
 |  1557  |   Medium   | [Minimum Number of Vertices to Reach All Nodes](Problems/1557.cpp)                               |
 |  1567  |   Medium   | [Maximum Length of Subarray With Positive Product](Problems/1567.cpp)                            |
+|  1579  |    Hard    | [Remove Max Number of Edges to Keep Graph Fully Traversable](Problems/1579.cpp)                  |
 |  1584  |   Medium   | [Min Cost to Connect All Points](Problems/1584.cpp)                                              |
 |  1609  |   Medium   | [Even Odd Tree](Problems/1609.cpp)                                                               |
 |  1615  |   Medium   | [Maximal Network Rank](Problems/1615.cpp)                                                        |
diff --git a/Templates/Union_Find.cpp b/Templates/Union_Find.cpp
@@ -7,6 +7,9 @@ public:
     iota(root.begin(), root.end(), 0);
   }
 
+  UnionFind(const UnionFind &uf)
+      : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {}
+
   int find(int x) {
     while (x != root[x]) x = root[x] = root[root[x]];
     return x;