Участник:S1td1kov/LargestComponentSizebyCommonFactor

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/largest-component-size-by-common-factor

//follow my github https://github.com/RusS1103/Leetcode
class dfs {
   public:
   vector<int> arr;
   dfs(int n) : arr(n){
       for (int i = 0;i < n; i++){
           arr[i]=i;
       }
   }
   void merge(int a, int b){
       arr[find(arr[a])]=arr[find(arr[b])];
   }
   int find(int x){
       if(arr[x]!=x){
           arr[x]=find(arr[x]);
       }
       return arr[x];
   }
   };
   class Solution{
   public:
   int largestComponentSize(vector<int>& A) {
       int n = *(max_element(A.begin(),A.end()));
       dfs DFS(n+1);
       for(auto x:A){
           int temp=sqrt(x);
           for(int k = 2;k <= temp; k++){
               if(x % k == 0){
                       DFS.merge(x,k);
                   DFS.merge(x,x/k);
               }
           }
       }
       unordered_map<int,int> m;
       int res = 1;
       for(auto v : A){
           m[DFS.find(v)]+=1;
           res=max(res,m[DFS.find(v)]);
       }
       return res;
   }
   };