3378. Count Connected Components in LCM Graph

You are given an array of integers nums of size n and a positive integer threshold.

There is a graph consisting of n nodes with the ith node having a value of nums[i]. Two nodes i and j in the graph are connected via an undirected edge if lcm(nums[i], nums[j]) <= threshold.

Return the number of connected components in this graph.

A connected component is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

The term lcm(a, b) denotes the least common multiple of a and b.

class Solution {
    int uf[101010];
    int find(int u) {
        return uf[u] == u ? u : uf[u] = find(uf[u]);
    }
    void uni(int u, int v) {
        int pu = find(u), pv = find(v);
        uf[pu] = uf[pv] = min(pu,pv);
    }
public:
    int countComponents(vector<int>& nums, int threshold) {
        int res = 0;
        for(int i = 0; i < nums.size(); i++) uf[i] = i;
        vector<int> cover(threshold + 1, -1);
        for(int i = 0; i < nums.size(); i++) {
            for(int j = nums[i]; j <= threshold; j += nums[i]) {
                if(cover[j] == -1) cover[j] = i;
                else {
                    uni(cover[j], i);
                    if(j == nums[i]) break;
                }
            }
        }
        for(int i = 0; i < nums.size(); i++) if(find(i) == i) res++;
        return res;
    }
};