# LeetCode 952: Largest Component Size by Common Factor

Posted on

Problem

I’m posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

### Problem

Given a non-empty array of unique positive integers A, consider the
following graph:

• There are nums.length nodes, labeled nums[0] to nums[nums.length - 1];

• There is an edge between nums[i] and nums[j] if and only if nums[i] and nums[j] share a common factor greater than 1.

• Return the size of the largest connected component in the graph.

### Example 1:

• Input: [4,6,15,35]
• Output: 4

### Example 2:

• Input: [20,50,9,63]
• Output: 2

### Example 3:

• Input: [2,3,6,7,4,12,21,39]
• Output: 8

### Note:

• $$1<=nums.length<=200001<=nums.length<=200001 <= nums.length <= 20000$$
• $$1<=nums[i]<=1000001<=nums[i]<=1000001 <= nums[i] <= 100000$$

### Inputs

[4,6,15,35]
[20,50,9,63]
[2,3,6,7,4,12,21,39]
[2,3,6,7,4,12,21,39,100,101,102,103,104,1200,123,123,13424]



### Outputs

4
2
8
15


### Code

#include <cstdint>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cmath>

#define max(a, b) (a > b ? a : b) // std::max(a, b)

// Union Find
struct DisjointSets {
DisjointSets(int_fast64_t n) : parent(n) {
for (int_fast64_t index = 0; index < n; index++) {
parent[index] = index;
}
}

void union_ds(const int_fast64_t x, const int_fast64_t y) {
parent[find_ds(x)] = parent[find_ds(y)];
}

const int_fast64_t find_ds(const int_fast64_t x) {
if (parent[x] != x) {
parent[x] = find_ds(parent[x]);
}

return parent[x];
}

private:
std::vector<int> parent;
};

struct Solution {
static const size_t largestComponentSize(const std::vector<int> &nums) {
const size_t max_nums = *std::max_element(nums.begin(), nums.end());
DisjointSets union_find(max_nums + 1);

for (const auto &num : nums) {
for (size_t k = 2; k <= std::sqrt(num); k++) {
if (num % k == 0) {
union_find.union_ds(num, k);
union_find.union_ds(num, num / k);
}
}
}

std::unordered_map<int, int> component_map;
size_t largest_component = 1;

for (const auto &num : nums) {
size_t curr_component = ++component_map[union_find.find_ds(num)];
largest_component = max(largest_component, curr_component);
}

return largest_component;
}
};



Solution

## Observation

I don't understand your solution.

## Code Review

#define max(a, b) (a > b ? a : b) // std::max(a, b)


Don't do this. Use std::max() directly.

Long gone are the days that we used macros to inline code like this. The std::max() will work correctly in all situation this macro has edge cased that will fail (especially if a or b are not just simple numbers).

The size_t is coming because you included a C header file cstdint. It is not guaranteed to be in the global namespace (it commonly is but its not guaranteed). So prefer to use std::size_t.

        const size_t max_nums = *std::max_element(nums.begin(), nums.end());