LeetCode 952: Largest Component Size by Common Factor

Question

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 <= 20000\$
• \$1 <= 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; } }; 

References

• Problem

• Discuss

• Solution

• Union Find

Answer 1

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 situations; this macro has edge cases that will fail (especially if a and 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 std::size_t max_nums = *std::max_element(nums.begin(), nums.end());