Leetcode 952: Largest Component Size by Common Factor

https://leetcode.com/problems/largest-component-size-by-common-factor/description/

Notes:

This question is apparently can be solved by Union-Find algorithm, but the key how to use it.

In order to find the connected components, we need to figure out the relationships which make the components connected.

For example, 2, 3, 6.

Without 6, 2 and 3 are not connected. However, 6 connects with both 2 and 3, thus all of them are connected.

Another way to say this is that 6 is connected with all of its factors (> 1).

So this gives us one of key observations: we can set up connections of A[i] with all its factors. Then we just need to count which group has the largest count.

See the code below:

class UF{
private:
    vector<int> ps;
public:
    UF(int n): ps(n) {
        for(int i=i; i<n; ++i) ps[i] = i;
    }
    int find(int i) {
        if(ps[i] != i) ps[i] = find(ps[i]);
        return ps[i];
    }
    void unite(int i, int j) {
        int a = find(i), b = find(j);
        if(a  != b) {
            ps[a] = b;
        }
    }
};

class Solution {
public:
    int largestComponentSize(vector<int>& A) {
        int m = *max_element(A.begin(), A.end());
        UF uf(m+1);
        for(auto &a : A) {
            for(int k=2; k*k<=a; ++k) {
                if(a % k == 0) {
                    uf.unite(a, k);
                    uf.unite(a, a/k);
                }
            }
        }
        int res = 1;
        unordered_map<int, int> mp;
        for(auto &a : A) {
            res = max(res, ++mp[uf.find(a)]);
        }
        return res;
    }
};