GCD Sort of an Array LeetCode solution in C++

1
class DSU {
2
  vector<int> par, rank;
3
  int n;
4

5
 public:
6
  DSU(int n) {
7
    this->par.resize(n);
8
    this->rank.resize(n);
9
    this->n = n;
10
    for (int i = 0; i < n; i++) par[i] = i;
11
  }
12
  int find(int x) {
13
    if (x == par[x]) return x;
14
    return par[x] = find(par[x]);
15
  }
16
  void Union(int a, int b) {
17
    int a_par = find(a);
18
    int b_par = find(b);
19
    if (a_par == b_par) return;
20
    if (rank[a_par] < rank[b_par]) {
21
      par[a_par] = b_par;
22
    } else if (rank[b_par] < rank[a_par]) {
23
      par[b_par] = a_par;
24
    } else {
25
      par[a_par] = b_par;
26
      rank[b_par] += 1;
27
    }
28
  }
29
};
30

31
class Solution {
32
 public:
33
  vector<int> spf;
34
  bool gcdSort(vector<int> &nums) {
35
    int n = nums.size();
36
    int max_nums = INT_MIN;
37
    for (int i = 0; i < n; i++) max_nums = max(max_nums, nums[i]);
38
    sieve(max_nums + 1);
39
    DSU dsu(max_nums + 1);
40
    vector<int> sortedNums(nums);
41
    sort(sortedNums.begin(), sortedNums.end());
42
    for (int i = 0; i < n; i++) {
43
      vector<int> factorsOfNumsi = getAllFactors(nums[i]);
44
      int numFactors = factorsOfNumsi.size();
45
      for (int j = 0; j < numFactors; j++) {
46
        dsu.Union(nums[i], factorsOfNumsi[j]);
47
      }
48
    }
49
    for (int i = 0; i < n; i++) {
50
      if (dsu.find(nums[i]) != dsu.find(sortedNums[i])) return false;
51
    }
52
    return true;
53
  }
54
  vector<int> getAllFactors(int x) {
55
    vector<int> factors;
56
    while (x > 1) {
57
      factors.push_back(spf[x]);
58
      x /= spf[x];
59
    }
60
    return factors;
61
  }
62
  void sieve(int n) {
63
    spf.resize(n);
64
    for (int i = 2; i < n; i++) spf[i] = i;
65
    for (int i = 2; i * i < n; i++) {
66
      if (spf[i] == i) {
67
        for (int j = i * i; j < n; j += i) {
68
          if (spf[j] > i) spf[j] = i;
69
        }
70
      }
71
    }
72
  }
73
};