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

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

建图 + 并查集

const int N = 1e5 + 10;
class Solution {
    
public:
    int p[N], cnt[N];
    int find(int x)
    {
    
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    int largestComponentSize(vector<int>& nums) {
    
        int n = nums.size();
        for(int i = 0; i < N; i ++) p[i] = i, cnt[i] = 0;

        for(int i = 0; i < n; i ++)
        {
    
            // 通过约数将各个数连接起来
            for(int j = 2; j <= nums[i] / j; j ++)
            {
    
                if(nums[i] % j == 0)
                {
    
                    int pa = find(nums[i]), pb = find(nums[i] / j), pc = find(j);
                    p[pb] = pa;
                    p[pc] = pa;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < n; i ++)
        {
    
            int pi = find(nums[i]);
            cnt[pi] ++; //查找数的根元素出现次数 ++
            res = max(res, cnt[pi]);
        }
        return res;
    }
};