leetcode

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

1319.cpp (1004B)

      1 class UnionFind {
      2     int n;
      3     vector<int> root, rank;
      4 
      5   public:
      6     UnionFind(int n) : n(n), root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }
      7 
      8     int find(int x) {
      9         while (x != root[x])
     10             x = root[x] = root[root[x]];
     11         return x;
     12     }
     13 
     14     void join(int x, int y) {
     15         if (x != y) {
     16             if (rank[x] > rank[y]) swap(x, y);
     17 
     18             root[x] = y;
     19             rank[y] += rank[x];
     20         }
     21     }
     22 
     23     int count() {
     24         int cnt = 0;
     25         for (int i = 0; i < n; i++)
     26             cnt += root[i] == i;
     27         return cnt;
     28     }
     29 };
     30 
     31 class Solution {
     32   public:
     33     int makeConnected(int n, vector<vector<int>> &connections) {
     34         int count = 0;
     35         UnionFind uf(n);
     36         for (auto &edge : connections) {
     37             int x = uf.find(edge[0]), y = uf.find(edge[1]);
     38             if (x == y)
     39                 count++;
     40             else
     41                 uf.join(x, y);
     42         }
     43         return count < uf.count() - 1 ? -1 : uf.count() - 1;
     44     }
     45 };