//
// Created by 高森森 on 2022/2/15.
//

#ifndef LEETCODE_SOLUTION46_H
#define LEETCODE_SOLUTION46_H
#include<iostream>
#include<vector>
#include <cmath>
#include <numeric>
#include<unordered_map>

using namespace std;
class UnionFind5{
public:
    vector<int>father;//父亲节点
    vector<int>rank;//秩的数
    int n;//节点个数
    int setCount;//连通分量数
public:
    //查询父结点
    UnionFind5(int _n):n(_n),setCount(_n),rank(_n,1),father(_n){
        //iota函数，令father[i]=i;
        iota(father.begin(),father.end(),0);
    }
    int find(int x){
        if(x==father[x])
            return x;
        else{
            father[x]=find(father[x]);
            return father[x];
        }
    }

    //并查集合并
   void merge(int i,int j){
        int x=find(i);
        int y=find(j);
        if(x!=y){
            if(rank[x]<=rank[y]){
                father[x]=y;
            }
            else{
                father[y]=x;
            }
            if(rank[x]==rank[y]&&x!=y)
                rank[y]++;
            setCount--;
        }
    }
    bool isConnected(int x,int y){
        x=find(x);
        y=find(y);
        return x==y;
    }
};

class Solution46 {
public:
    int largestComponentSize(vector<int>& nums) {
        int maxNum=0;
        for(int num:nums){
            maxNum=max(num,maxNum);
        }
        int n=nums.size();
        UnionFind5 unionFind5(maxNum+1);
        for(int num:nums){
            for(int i=sqrt(num);i>=2;i--){
                if(num%i==0){
                    unionFind5.merge(num,i);
                    unionFind5.merge(num,num/i);
                }
            }
        }
        int res=0;
        unordered_map<int,int>map;
        for(int num:nums){
            map[unionFind5.find(num)]++;
        }
        for(auto it=map.begin();it!=map.end();it++){
            res=max(res,it->second);
        }
        return  res;
    }
};


#endif //LEETCODE_SOLUTION46_H