Largest Component Size by Common Factor LeetCode solution in C++

1
class Solution {
2
 private:
3
  vector<bool> sieve(int n) {
4
    vector<bool> prime(n + 1);
5
    for (int i = 0; i <= n; i++) prime[i] = 1;
6
    for (int p = 2; p * p <= n; p++) {
7
      if (prime[p] == 1) {
8
        for (int i = p * p; i <= n; i += p) prime[i] = 0;
9
      }
10
    }
11
    prime[1] = prime[0] = 0;
12
    return prime;
13
  }
14
  vector<int> factors(int n, vector<int> &primelist) {
15
    vector<int> facs;
16
    for (int i = 0; primelist[i] * primelist[i] <= n && i < primelist.size(); i++) {
17
      if (n % primelist[i] == 0) {
18
        facs.push_back(primelist[i]);
19
        while (n % primelist[i] == 0) {
20
          n /= primelist[i];
21
        }
22
      }
23
    }
24
    if (n > 1) facs.push_back(n);
25
    return facs;
26
  }
27
  void dfs(vector<vector<int>> &gr, int node, vector<int> &vis, int &compSize) {
28
    if (vis[node]) return;
29
    vis[node] = 1;
30
    compSize++;
31
    for (auto x : gr[node]) {
32
      dfs(gr, x, vis, compSize);
33
    }
34
  }
35

36
 public:
37
  int largestComponentSize(vector<int> &nums) {
38
    int n = nums.size();
39
    vector<vector<int>> gr(n);
40
    vector<bool> prime = sieve(1e5 + 6);
41
    vector<int> primelist;
42
    // Getting all the primes till 10^5 as maximum value of nums[i] is 10^5
43
    for (int i = 2; i <= 1e5 + 5; i++)
44
      if (prime[i]) primelist.push_back(i);
45
    unordered_map<int, int> m; // to store the index of the node with prime factor x
46
    for (int i = 0; i < n; i++) {
47
      vector<int> facs = factors(nums[i], primelist);
48
      for (auto j : facs) {
49
        if (m.find(j) == m.end()) { // prime factor had not occured before
50
          m[j] = i;                 // j is the prime factor and its index is i
51
        } else {
52
          // prime factor has already been seen before in a previous number and
53
          // nums[i] is connected to that number
54
          gr[i].push_back(m[j]);
55
          gr[m[j]].push_back(i);
56
        }
57
      }
58
    }
59
    int ans = 0;
60
    vector<int> vis(n);
61
    for (int i = 0; i < n; i++) { // running a simple dfs to calculate the maximum component size
62
      if (!vis[i]) {
63
        int compSize = 0;
64
        dfs(gr, i, vis, compSize);
65
        ans = max(ans, compSize);
66
      }
67
    }
68
    return ans;
69
  }
70
};