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());