952 Largest Component Size by Common Factor

952. Largest Component Size by Common Factor

1. Question

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

• There areA.lengthnodes, labelledA[0]toA[A.length - 1];

• There is an edge betweenA[i]andA[j]if and only if A[i]andA[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

2. Implementation

(1) Union Find

思路: 对于每个数，我们找出所有它的factor，将它自己与factor通过union-find联合起来， 最后遍历一遍输入数组，通过union-find找到其所属的component，看看哪个component包含输入数组的数字最多即可

class Solution {
    public int largestComponentSize(int[] A) {
        int maxNum = 0;

        for (int num : A) {
            maxNum = Math.max(maxNum, num);
        }

        UnionFind uf = new UnionFind(maxNum + 1);

        for (int num : A) {
            int upperBound = (int)Math.sqrt(num);

            for (int factor = 2; factor <= upperBound; factor++) {
                if (num % factor == 0) {
                    uf.union(num, factor);
                    uf.union(num, num / factor);
                }
            }
        }

        int res = 0;
        Map<Integer, Integer> map = new HashMap();

        for (int num : A) {
            int root = uf.find(num);
            map.put(root, map.getOrDefault(root, 0) + 1);
            res = Math.max(res, map.get(root));
        }
        return res;
    }

    class UnionFind {
        int[] root;
        int[] size;
        int maxSize;

        public UnionFind(int n) {
            root = new int[n];
            size = new int[n];

            for (int i = 0; i < n; i++) {
                root[i] = i;
                size[i] = 1;
            }
        }

        public int find(int node) {
            while (node != root[node]) {
                node = root[node];
            }
            return node;
        }

        public void union(int i, int j) {
            int p = find(i);
            int q = find(j);

            if (p == q) return;

            if (size[p] < size[q]) {
                root[p] = q;
                size[q] += size[p];
            }
            else {
                root[q] = p;
                size[p] += size[q];
            }
        }
    }
}

3. Time & Space Complexity

Union Find: 时间复杂度O(n * Sqrt(W)), n是输入数组的size，W是输入数组的最大数。空间复杂度O(W)