leetcode-952: Calculate max component size by common factor

题目

题目连接
给定一个由不同正整数的组成的非空数组 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

解题

方法一：Weighted directed graph+并查集（超时）

带权重的图+并查集

写法一：

Each node also carries weightsweight[i],表示直接指向当前节点的 节点个数
In the end, only the one with the largest weight needs to be found,就是我们想要的答案.

能直接遍历weightto get the maximum number of set elements？Obviously it can't be done directly,He also needs to compress the path,Make the element point directly to the root node.

class UnionFind{
    
private:
    vector<int> parent;
    vector<int> weight;
public:
    UnionFind(int n){
    
        parent.resize(n);
        weight.resize(n);
        for(int i=0;i<n;i++){
    
            parent[i]=i;
            weight[i]=1;//Points directly to the number of the current node(包含自身,Note the grandchild nodes,Not directly pointing)
        }
    }
    int find(int index){
    
        if(parent[index]==index) return index;
        int origin=parent[index];
        parent[index]=find(parent[index]);
        weight[parent[index]]++;//The number of nodes pointing to the root node+1
        weight[origin]--;//The number of nodes pointing to the original node-1
        return parent[index];
    }

    void unite(int index1,int index2){
    
        int p1=find(index1);
        int p2=find(index2);
        if(p1!=p2){
    
            parent[p1]=p2;
            weight[p2]++;//The number of nodes pointing to the root node+1
        }
    }
    int findMaxSet(){
    
        for(int i=0;i<weight.size();i++){
    
            find(i);
        }
        int res=0;
        for(int i=0;i<weight.size();i++){
    
            res=max(res,weight[i]);
        }
        return res;
    }
};

class Solution {
    
public:
    int largestComponentSize(vector<int>& nums) {
    
        int n=nums.size();
        UnionFind uf(n);

        unordered_map<int,int> mp;
        int id=0;
        for(int i=0;i<n;i++){
    
            if(!mp.count(nums[i])){
    
                mp[nums[i]]=id++;
            }
        }

        for(int i=0;i<n;i++){
    
            for(int j=i+1;j<n;j++){
    
                int id1=mp[nums[i]];
                int id2=mp[nums[j]];
                if(gcd(nums[i],nums[j])>1){
    
                    uf.unite(id1,id2);
                }
            }
        }
        return uf.findMaxSet();
    }
};

写法二：
weight表示,The number of nodes pointing to the current node(Contains grandchild nodes, etc)
只要在uniteAdd all nodes of another subtree to it 数就行了,findPath compression during the process,Just adjusted to point to the root node,However, the number of all nodes of the root node will not change.

class UnionFind{
    
private:
    vector<int> parent;
    vector<int> weight;
public:
    UnionFind(int n){
    
        parent.resize(n);
        weight.resize(n);
        for(int i=0;i<n;i++){
    
            parent[i]=i;
            weight[i]=1;//Points to the number of current nodes（Contains grandchild nodes, etc）
        }
    }
    int find(int index){
    
        if(parent[index]==index) return index;
        parent[index]=find(parent[index]);
        return parent[index];
    }

    void unite(int index1,int index2){
    
        int p1=find(index1);
        int p2=find(index2);
        if(p1!=p2){
    
            parent[p1]=p2;
            weight[p2]+=weight[p1];//The number of nodes pointing to the root node 加上 子树的节点数量
        }
    }
    int findMaxSet(){
    
        for(int i=0;i<weight.size();i++){
    
            find(i);
        }
        int res=0;
        for(int i=0;i<weight.size();i++){
    
            res=max(res,weight[i]);
        }
        return res;
    }
};

class Solution {
    
public:
    int largestComponentSize(vector<int>& nums) {
    
        int n=nums.size();
        UnionFind uf(n);

        unordered_map<int,int> mp;
        int id=0;
        for(int i=0;i<n;i++){
    
            if(!mp.count(nums[i])){
    
                mp[nums[i]]=id++;
            }
        }

        for(int i=0;i<n;i++){
    
            for(int j=i+1;j<n;j++){
    
                int id1=mp[nums[i]];
                int id2=mp[nums[j]];
                if(gcd(nums[i],nums[j])>1){
    
                    uf.unite(id1,id2);
                }
            }
        }
        return uf.findMaxSet();
    }
};

The main reason for the timeout is because of two layersfor循环

方法二：枚举质因数+并查集

参考链接

基本思路：Add the associated ones to the union set,最后遍历nums,The same number of root nodes+1,This will find the set with the most elements.

由于nums.length最大为$2\ast 10^4$lianjie
遍历每个值,A pairwise match will time out.

Therefore, the method of enumerating common factors is adopted,如果k>=2,且num%k==0,那么kis a common divisor,对num和k进行联结,以及num和num/k进行联结.不管k或者num/k有没有在numsIt doesn't matter,Because of the back traversalnumswill not traverse them.
相比$O(4\ast 10^8)$The complexity is smaller.

class UnionFind{
    
private:
    vector<int> parent;
public:
    UnionFind(int n){
    
        parent.resize(n);
        for(int i=0;i<n;i++){
    
            parent[i]=i;
        }
    }
    int find(int index){
    
        if(parent[index]==index) return index;
        return parent[index]=find(parent[index]);
    }

    void unite(int index1,int index2){
    
        int p1=find(index1);
        int p2=find(index2);
        if(p1==p2) return;
        parent[p1]=p2;
    }
};

class Solution {
    
public:
    int largestComponentSize(vector<int>& nums) {
    
        int maxLength=*max_element(nums.begin(),nums.end());
        int n=nums.size();
        UnionFind uf(maxLength+1);

        for(int num:nums){
    
            for(int k=sqrt(num);k>=2;k--){
    
                if(num%k==0){
    
                    uf.unite(num,k);//不管k属不属于num都没有关系,Add him to the collection.Because it has to be traversed again laternums
                    uf.unite(num,num/k);
                }
            }
        }
        vector<int> cnt(maxLength+1);
        int res=0;
        for(int num:nums){
    //遍历nums中的值,of the same set+1
            cnt[uf.find(num)]++;
            res=max(res,cnt[uf.find(num)]);
        }
    
        return res;
    }
};