题目描述

给定一个由不同正整数的组成的非空数组 A，考虑下面的图：

• 有 A.length 个节点，按从 A[0] 到 A[A.length - 1] 标记；
• 只有当 A[i] 和 A[j] 共用一个大于 1 的公因数时，A[i] 和 A[j] 之间才有一条边。

返回图中最大连通组件的大小。

样例

输入：[4,6,15,35]
输出：4

输入：[20,50,9,63]
输出：2

输入：[2,3,6,7,4,12,21,39]
输出：8

注意

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

算法

(数学，并查集) $O(n \sqrt{X})$

1. 对每个数字分别分解质因数，开一个二维 vector 记录每个质因数所对应的数字有哪些。
2. 对每个质因数，将其记录的所有数字通过并查集连接在一起。
3. 最大的集合即为答案。
4. 由于每个数字最多只有 6 个不同的质因数 (最坏情况下为2 * 3 * 5 * 7 * 11 * 13)，所以这个二维 vector 只会存放 $O(n)$ 个数字。

时间复杂度

• 对每个数字寻找质因数的时间复杂度为 $O(\sqrt{X})$，$X$ 为数字的最大值，并查集操作时间近似为常数，故总时间复杂度为 $O(n \sqrt{X})$。

C++ 代码

class Solution {
public:
    vector<int> fa, sz;

    int find(int x) {
        return x != fa[x] ? fa[x] = find(fa[x]) : x;
    }

    int largestComponentSize(vector<int>& A) {
        int n = A.size(), ans = 0;
        vector<vector<int>> num(100001);

        for (int i = 0; i < n; i++) {
            int x = A[i];
            for (int y = 2; y * y <= x; y++) {
                if (x % y == 0)
                    num[y].push_back(i);
                while (x % y == 0)
                    x /= y;
            }
            if (x > 1)
                num[x].push_back(i);
        }

        fa = vector<int>(n);
        sz = vector<int>(n);

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

        for (int i = 1; i <= 100000; i++)
            for (int j = 1; j < num[i].size(); j++) {
                int x = num[i][0], y = num[i][j];
                int fx = find(x), fy = find(y);
                if (fx != fy) {
                    if (sz[fx] < sz[fy]) {
                        fa[fy] = fx;
                        sz[fx] += sz[fy];
                    }
                    else {
                        fa[fx] = fy;
                        sz[fy] += sz[fx];
                    }
                }
            }

        for (int i = 0; i < n; i++)
            if (i == find(i))
                ans = max(ans, sz[i]);

        return ans;
    }
};