leetcode

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

0547.cpp (938B)

      1 class UnionFind {
      2     vector<int> root, rank;
      3     int n;
      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         x = find(x), y = find(y);
     16 
     17         if (x != y) {
     18             if (rank[x] > rank[y]) swap(x, y);
     19 
     20             root[x] = y;
     21             rank[y] += rank[x];
     22         }
     23     }
     24 
     25     int count() {
     26         int cnt = 0;
     27         for (int i = 0; i < n; i++)
     28             cnt += root[i] == i;
     29         return cnt;
     30     }
     31 };
     32 
     33 class Solution {
     34   public:
     35     int findCircleNum(vector<vector<int>> &isConnected) {
     36         int n = isConnected.size();
     37         UnionFind uf(n);
     38         for (int i = 0; i < n; i++)
     39             for (int j = i + 1; j < n; j++)
     40                 if (isConnected[i][j]) uf.join(i, j);
     41 
     42         return uf.count();
     43     }
     44 };