leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1579.cpp (1392B)

      1 class UnionFind {
      2     int n, cnt = n;
      3     vector<int> root, size;
      4 
      5   public:
      6     UnionFind(int n) : n(n), root(n), size(n, 1) { iota(root.begin(), root.end(), 0); }
      7 
      8     UnionFind(const UnionFind &uf) : n(uf.n), cnt(uf.cnt), root(uf.root), size(uf.size) {}
      9 
     10     static int redundant;
     11 
     12     int find(int x) {
     13         while (x != root[x])
     14             x = root[x] = root[root[x]];
     15         return x;
     16     }
     17 
     18     void join(int x, int y) {
     19         x = find(x), y = find(y);
     20         if (x != y) {
     21             if (size[x] > size[y]) swap(x, y);
     22             root[x] = y;
     23             size[y] += size[x];
     24             cnt--;
     25         } else
     26             redundant++;
     27     }
     28 
     29     int count() { return cnt; }
     30     bool connected(int x, int y) { return find(x) == find(y); }
     31 };
     32 
     33 int UnionFind::redundant = 0;
     34 
     35 class Solution {
     36   public:
     37     int maxNumEdgesToRemove(int n, vector<vector<int>> &e) {
     38         UnionFind::redundant = 0;
     39 
     40         UnionFind a(n + 1);
     41         for (int i = 0; i < e.size(); i++)
     42             if (e[i][0] == 3) a.join(e[i][1], e[i][2]);
     43 
     44         UnionFind b = a;
     45         for (int i = 0; i < e.size(); i++)
     46             if (e[i][0] == 1)
     47                 a.join(e[i][1], e[i][2]);
     48             else if (e[i][0] == 2)
     49                 b.join(e[i][1], e[i][2]);
     50 
     51         // count must be 2, since 0 is not used
     52         return a.count() == 2 && b.count() == 2 ? UnionFind::redundant : -1;
     53     }
     54 };