LargestComponentSizeByCommonFactor.java

class LargestComponentSizeByCommonFactor {
    
    private int[] parent;

    public int largestComponentSize(int[] A) {
        int maxVal = 1;
        for (int num : A) {
            if (num > maxVal) {
                maxVal = num;
            }
        }
        parent = new int[maxVal + 1];
        for (int i = 1; i <= maxVal; i++) {
            parent[i] = i;
        }
        for (int num : A) {
            for (int f = 2; f * f <= num; f++) {
                if (num % f == 0) {
                    union(num, f);
                    union(num, num / f);
                }
            }
        }
        int maxCount = 1;
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : A) {
            int root = find(num);
            Integer count = countMap.get(root);
            if (count == null) {
                countMap.put(root, 1);
            } else {
                countMap.put(root, count + 1);
                if (count + 1 > maxCount) {
                    maxCount = count + 1;
                }
            }
        }
        return maxCount;
    }

    public int find(int p) {
        int root = p;
        while (root != parent[root]) {
            root = parent[root];
        }
        while (p != root) {
            int newp = parent[p];
            parent[p] = root;
            p = newp;
        }
        return root;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) {
            return;
        }
        parent[rootP] = rootQ;
    }
    
}