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

链接：952.按公因数计算最大组件大小
难度：Hard
标签：并查集、数组、哈希表、数学、数论
简介：返回 图中最大连通组件的大小 。

题解 1 - cpp

• 编辑时间：2022-07-31
• 执行用时：308ms
• 内存消耗：128.8MB
• 编程语言：cpp
• 解法介绍：对于合数先进行合并。

class UnionFind {
   public:
    vector<int> list;
    UnionFind(int len) {
        list = vector<int>(len);
        for (int i = 0; i < len; i++) list[i] = i;
    }
    int find(int idx) {
        if (list[idx] == idx) return idx;
        int p = find(list[idx]);
        list[idx] = p;
        return p;
    }
    void uni(int idx1, int idx2) {
        int p1 = find(idx1), p2 = find(idx2);
        if (p1 == p2) return;
        list[p1] = p2;
    }
};
#define MAX 2e5
class Solution {
   public:
    int largestComponentSize(vector<int>& nums) {
        int n = nums.size();
        UnionFind uf(MAX);
        for (int num : nums) {
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    uf.uni(num, i);
                    uf.uni(num, num / i);
                }
            }
        }
        int ans = 0;
        unordered_map<int, int> m;
        for (auto& num : nums) {
            int p = uf.find(num);
            m[p]++;
            ans = max(ans, m[p]);
        }
        return ans;
    }
};