Largest Component Size by Common Factor (H)

题目

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. 1 <= A.length <= 20000
2. 1 <= A[i] <= 100000

题意

给定一串正整数，将其中具有相同因数(>=2)的整数两两相连，求这样操作后最大连通分量中结点的数量。

思路

并查集处理。对于每一个整数，找到它所有大于2的因数，将该因数和整数本身添加到一个组中。最后统计每个组中数组中整数出现的次数即可。

代码实现

Java

class Solution {
    public int largestComponentSize(int[] A) {
        int maxSize = 0, maxNum = 0;
        // 找到最大整数
        for (int num : A) {
            maxNum = Math.max(maxNum, num);
        }

        Map<Integer, Integer> map = new HashMap<>();
        int[] root = new int[maxNum + 1];
        for (int i = 1; i <= maxNum; i++) {
            root[i] = i;
        }

        for (int num : A) {
            for (int i = 2; i <= (int) Math.sqrt(num); i++) {
                if (num % i == 0) {
                    int j = num / i;
                    union(root, num, i);
                    union(root, num, j);
                }
            }
        }

        for (int num : A) {
            int tmp = findRoot(root, num);
            int size = map.getOrDefault(tmp, 0) + 1;
            map.put(tmp, size);
            maxSize = Math.max(maxSize, size);
        }

        return maxSize;
    }

    private void union(int[] root, int x, int y) {
        int rootX = findRoot(root, x), rootY = findRoot(root, y);
        if (rootX != rootY) {
            root[rootX] = rootY;
        }
    }

    private int findRoot(int[] root, int x) {
        // 路径压缩
        return root[x] == x ? x : (root[x] = findRoot(root, root[x]));
    }
}