Most Stones Removed with Same Row or Column LeetCode solution in C++

1
class Solution {
2
  class UnionFind {
3
    vector<int> parent, rank;
4

5
   public:
6
    int count = 0;
7
    UnionFind(int n) {
8
      count = n;
9
      parent.assign(n, 0);
10
      rank.assign(n, 0);
11
      for (int i = 0; i < n; i++) {
12
        parent[i] = i;
13
      }
14
    }
15
    int find(int p) {
16
      while (p != parent[p]) {
17
        parent[p] = parent[parent[p]];
18
        p = parent[p];
19
      }
20
      return p;
21
    }
22
    bool Union(int p, int q) {
23
      int rootp = find(p);
24
      int rootq = find(q);
25
      if (rootp == rootq)
26
        return false;
27
      else if (rank[rootp] < rank[rootq]) {
28
        parent[rootp] = rootq;
29
        rank[rootq]++;
30
        count--;
31
        return true;
32
      } else {
33
        parent[rootq] = rootp;
34
        rank[rootp]++;
35
        count--;
36
        return true;
37
      }
38
    }
39
  };
40

41
 public:
42
  int removeStones(vector<vector<int>> &stones) {
43
    int n = stones.size();
44
    UnionFind uf(n);
45
    for (int i = 0; i < n; i++) {
46
      for (int j = 0; j < i; j++) {
47
        if (stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]) uf.Union(i, j);
48
      }
49
    }
50

51
    return n - uf.count;
52
  }
53
};