【数学, 并查集】按公因数计算最大组件大小

题目

952. 按公因数计算最大组件大小

---

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= nums.length <= 2 * 10^4
• 1 <= nums[i] <= 10^5
• nums 中所有值都 不同

解题

方法一：数学 并查集

思路

很明显的并查集题，合并的条件是：两个节点的值共用一个大于 1 的因子(公因数)。

那么对于 nums 中的每一个数(num)，把其分成两个因数相乘，那么这三个数就在同一个连通图中，也就是说：

对于范围 $[2, \sqrt{num}]$ 内的每个正整数，如果它是 num 的因数(factor)，那么 $\frac{num}{factor}$ 就是 num 的另一个因数，它们三个数属于同一个“组件”。

由于遍历因子的时候，很多不在 nums 中的数也会被连入组件中，为了排除这些数的干扰，应该在并查集中初始化这些数。由于所有这些数都是 nums 中的数或者它们的因数，那么它们都小于 nums 中最大的数，故并查集应该初始化的范围是：$[1, max(nums)]$。

接下来就是把符合条件的节点合并，然后找到 图中最大连通组件的大小 (由于需要快速的知道哪些节点在同一个连通图中所以要使用按秩合并的并查集)。

代码

class Solution {
    private int[] root, rank;

    public int largestComponentSize(int[] nums) {
        int maxNum = 0;
        for (int num : nums) {
            if (num > maxNum) maxNum = num;
        }
        root = new int[maxNum + 1];
        rank = new int[maxNum + 1];
        for (int i = 0; i <= maxNum; i++) root[i] = i;
        for (int num : nums) {
            for (int factor = 2; factor * factor <= num; factor++) {
                if (num % factor == 0) {
                    union(num, factor);
                    union(num, num / factor);
                }
            }
        }
        int ans = 0;
        int[] counts = new int[maxNum + 1];
        for (int num : nums) {
            int numRoot = find(num);
            if (++counts[numRoot] > ans) ans = counts[numRoot];
        }

        return ans;
    }

    private int find(int n) {
        return root[n] == n ? n : (root[n] = find(root[n]));
    }

    private void union(int p, int q) {
        int rootP = find(p), rootQ = find(q);
        if (rootP == rootQ) return;
        if (rank[rootP] < rank[rootQ]) root[rootP] = rootQ;
        else {
            root[rootQ] = rootP;
            if (rank[rootP] == rank[rootQ]) rank[rootP]++;
        }
    }
}

class Solution {
private:
    int root[100010] = {0};
    int rank[100010] = {0};

    int find(const int& n) {
        return root[n] == n ? n : (root[n] = find(root[n]));
    }

    void join(const int& p, const int& q) {
        const int& rp = find(p), rq = find(q);
        if (rp == rq) return;
        if (rank[rp] < rank[rq]) root[rp] = rq;
        else {
            root[rq] = rp;
            if (rank[rp] == rank[rq]) rank[rp]++;
        }
    }

public:
    int largestComponentSize(vector<int>& nums) {
        const int& max_num = *max_element(nums.begin(), nums.end());
        for (int i = 0; i <= max_num; i++) root[i] = i;
        for (int num : nums) {
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    join(num, i);
                    join(num, num / i);
                }
            }
        }
        int ans = 0, counts[100010] = {0};
        for (const int& num : nums) {
            const int& num_root = find(num);
            if (++counts[num_root] > ans) ans = counts[num_root];
        }
        
        return ans;
    }
};