Largest Component Size by Common Factor

LeetCode Solutions

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

There are A.length nodes, labeled A[0] to A[A.length - 1].

An edge exists between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

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

Note:

1 <= A.length <= 20000
1 <= A[i] <= 100000

Solution: Union-Find + Brute Force

#define MAX_N 121000

class Solution {
public:
    int largestComponentSize(vector<int>& A) {
        // First 100000 positions hold all common factors of A[i]
        // Last 20000 positions handle up to 20000 elements
        for(int i=0;i<MAX_N;++i)
            parent[i]=i;
        fill(count, count+MAX_N, 0);
        
        for(int i=0;i<A.size();++i) {
            count[100001+i]=1;
            // Connect factors
            for(int j=2;j*j<=A[i];++j) {
                if (A[i]%j==0) {
                    unite(j, 100001+i);
                    unite(A[i]/j, 100001+i);
                }
            }
            // Connect all factors with input numbers
            unite(A[i], 100001+i);
        }
        
        // Return group with most nodes
        int res=1;
        for(int i=0;i<A.size();++i)
            res = max(res, count[find(100001+i)]);
        return res;
    }
    
    // Union-find structure
    void unite(int a, int b) {
        int i=find(a);
        int j=find(b);
        if (i==j) return;
        count[i]+=count[j];
        parent[j]=i;
    }
    
    int find(int a) {
        if (parent[a]==a) return a;
        return parent[a] = find(parent[a]);
    }
    
    int parent[MAX_N];
    int count[MAX_N];
};

You can use path compression to make lookups faster:

void unite(int a, int b) {
    int i=find(a);
    int j=find(b);
    if (i==j) return;
    if (rank[i]<rank[j]) {
        parent[i]=j;
        count[j]+=count[i];
    } else {
        parent[j]=i;
        count[i]+=count[j];
        if (rank[i]==rank[j]) ++rank[i];
    }
}

int find(int a) {
    if (parent[a]==a) return a;
    return parent[a] = find(parent[a]);
}

int parent[MAX_N];
int count[MAX_N];
int rank[MAX_N];

#union-find

Isomorphic Strings Longest Substring Without Repeating Characters