952. Largest Component Size by Common Factor

Version #1 Union Find
The KEY point is -> a Union Find graph is not necessary to have only the components that we care
In this question, the graph contains 2 kinds of elements -> 1 is the numbers, 2 is the factor of the numbers
When we are calculating the size of each connected component, we can only count the #root for each number



50.00 %
class Solution {
    private int[] id;
private int[] size;
public int largestComponentSize(int[] A) {
int N = 0;
for (int a : A) {
N = Math.max(N, a);
}
N++;
id = new int[N];
size = new int[N]; // this size contains both the factors and the original a numbers
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
for (int a : A) {
for (int i = 2; i <= Math.sqrt(a); i++) {
if (a % i == 0) {
union(a, i);
union(a, a / i);
}
}
}
Map<Integer, Integer> counter = new HashMap<>();
int max = 0;
for (int a : A) {
int root = root(a);
int count = 1 + counter.getOrDefault(root, 0);
counter.put(root, count);
max = Math.max(max, count);
}
return max;
}

private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

public boolean union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return false;
}
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
return true;
}
}