952. Largest Component Size by Common Factor

952. Largest Component Size by Common Factor

Question:

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

• There are A.length nodes, labelled A[0] to A[A.length - 1];
• There is an edge 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.

Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8

Note:

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

Solution:

• Method 1: Union find set

   class Solution {
        private int[] uf;
        public int largestComponentSize(int[] A) {
            if(A == null || A.length == 0) return 0;
            int max = A[0];
            for(int i = 1; i < A.length; i++) max = Math.max(max, A[i]);
            this.uf = new int[max + 1];
            for(int i = 0; i < uf.length; i++) this.uf[i] = i;
            // For every number, find their factor and add to uf.
            for(int i = 0; i < A.length; i++){
                for(int j = 2; j <= (int)Math.sqrt(A[i]); j++){
                    if(A[i] % j == 0){
                        union(A[i], j);
                        union(A[i], A[i] / j);
                    }
                }
            }
            Map<Integer, Integer> map = new HashMap<>();
            int res = 1;
            for(int i = 0; i < A.length; i++){
                int root = find(A[i]);
                int cur = map.containsKey(root) ? map.get(root): 0;
                map.put(root, ++cur);
                res = Math.max(res, cur);
            }
            return res;
        }
        private void union(int i, int j){
            int p = find(i);
            int q = find(j);
            uf[p] = q;
        }
        private int find(int j){
            if(uf[j] != j){
                uf[j] = find(uf[j]);
            }
            return uf[j];
        }
    }
  

Reference

1. 花花酱 LeetCode 952. Largest Component Size by Common Factor