一开始想法单纯，试了试并查集+GCD，果断TLE 73

实在想不出比O(n^2)更好的算法，所以偷瞄了大神的代码，如下

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define _for(i,a,b) for(int i = (a);i < (b);i ++) 5  6 using namespace std; 7  8 const int maxn = 100039; 9 set
        
          g[maxn];10 vector
         
           f[maxn];11 bool fvis[maxn] {
   0},gvis[maxn] {
   0};12 class Solution13 {14     public:15         void demo(int x,int id)16         {17             for(int i = 2;i*i <= x;i ++)18             {19                 if(!(x%i))20                 {21                     f[id].push_back(i);//factor in vector22                     g[i].insert(id);//index in set23                     while(!(x%i)) x /= i;24                 }25             }26             if(x>1)27             {28                 f[id].push_back(x);//factor in vector29                 g[x].insert(id);//index in set30             }31         }32         void dfs(int id,set
          
            &S)33 {34 fvis[id] = true;35 S.insert(id);36 for(auto fac:f[id])37 {38 if(gvis[fac]) continue;39 gvis[fac] = true;40 for(auto fidx:g[fac])41 {42 if(fvis[fidx]) continue;43 S.insert(fidx);44 dfs(fidx,S);45 }46 }47 }48 int largestComponentSize(vector
           
            & A)49 {50 _for(i,0,A.size())51 demo(A[i],i);52 int rnt = 1;53 _for(i,0,A.size())54 {55 set
            
              tmp;56 if(fvis[i]) continue;57 dfs(i,tmp);58 rnt = max(rnt,(int)tmp.size());59 }60 return rnt;61 }62 };63 int main()64 {65 Solution obj;66 vector
             
               A { 2,3,6,7,4,12,21,39};67 cout << obj.largestComponentSize(A) << endl;68 return 0;69 }
             
            
           
          
         
        
       
      
     

稍微解释一下，大神搞了一个双射，f里装的都是A[i]的因子，g里装的都是因子的下标，比如g[2]里装的就都是偶数的A的元素的下标，然后dfs vector f，走一遍因子，再根据因子从set g里找下标，每找到一个下标就装到set里，这其实就是一个"集"，最后看看集的大小就是组件的大小，最大的集就是最大组件的大小