Minimize Hamming Distance After Swap Operations LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<int> parents;
4
  vector<int> ranks;
5
  int find(int a) {
6
    if (a == parents[a]) return parents[a];
7
    return parents[a] = find(parents[a]);
8
  }
9

10
  void uni(int a, int b) {
11
    a = find(a);
12
    b = find(b);
13

14
    if (ranks[a] >= ranks[b]) {
15
      parents[b] = a;
16
      ranks[a]++;
17
    } else {
18
      parents[a] = b;
19
      ranks[b]++;
20
    }
21
  }
22

23
  int minimumHammingDistance(vector<int> &source, vector<int> &target,
24
                             vector<vector<int>> &allowedSwaps) {
25
    int n = source.size();
26
    ranks = vector<int>(n, 0);
27

28
    for (int i = 0; i < n; i++) {
29
      parents.push_back(i);
30
    }
31

32
    for (auto &v : allowedSwaps) uni(v[0], v[1]);
33
    vector<unordered_multiset<int>> subs(n);
34

35
    for (int i = 0; i < n; i++) {
36
      subs[find(i)].insert(source[i]);
37
    }
38
    int cnt = 0;
39
    for (int i = 0; i < n; i++) {
40
      if (!subs[parents[i]].count(target[i]))
41
        cnt++;
42
      else
43
        subs[parents[i]].erase(subs[parents[i]].find(target[i]));
44
    }
45
    return cnt;
46
  }
47
};