Clear Solution using Union Find (N log(M)) (C++)
Intuition\nThe questions revolves around finding the maximum length of a connected component in a graph. Thus, we should naturally think in direction of Union F
# Intuition\nThe questions revolves around finding the maximum length of a connected component in a graph. Thus, we should naturally think in direction of **Union Find** Incase you can\'t figure this out I think you should do some related graph questions before jumping here!\n\n# Approach\nWe know that nums[i] and nums[j] for any i != j  share an edge if both have any common factor greater than 1. \n\nSo we can do prime factorisation of all the number and maintain a  {prime , vector of nums} map. Now we will union all the num within mapped to a single prime number as they can be grouped in one connected component. \n\nEg : nums: { 4,6,15,35} then map will contain \n{\n{2: {4,6}},\n{3: {6,15}},\n{5: {15,35}},\n{7: {35} }\n}\n\nNow we will union all the number within a vector mapped to a prime number. \nFor 2 we will union 4,6. Similarly we will union 6,15 for prime = 3. And so on.\n\nNow our DSU will have one connected component of size 4. Thus we will return 4. In this case we have only one connected component. Try with different numbers!\n\nAtlast we will find the maximum size among all the components.\n\n# Complexity\n- Time complexity:\nConsidering the Union-Find to be constant we have N * sqrt(M) where M is max element in the array.\n\n- Space complexity:\nO(M) where M is max element in array.\n\n# Code\n```\n struct dsu{\n     \n      vector <int> par,size;\n  \n     dsu(int n) {\n      \n         par.resize(n);\n         size.resize(n,1);\n        for (int i=0;i<n;i++) {\n             par[i]=i;\n           \n         }\n     }\n     \n     int find(int x)  {\n         if (par[x]==x) {return x;}\n         return par[x]=find(par[x]);\n     }\n   \n     void _union(int x,int y)  {\n         x=find(x);y=find(y);\n         if (x!=y) {\n           // add subtree with larger parent to subtree with smaller parent and update the size\n            if (x < y) {\n    par[y]=x;\n             size[x]+=size[y];size[y]=0;\n            }\n            else {\n                    par[x]=y;\n             size[y]+=size[x];\n             size[x]=0;\n            }\n         \n          \n         }\n     }\n     \n };\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        unordered_map < int , set <int> > mp;\n    int mx=0;\n        for (auto i:nums) {\n         int n=i;mx=max(n,mx);\n               while (i%2 == 0) {\n                   i=i/2;\n                   mp[2].insert(n);\n               }\n\n               for (int j=3;j*j<=i;j++) {\n                  while (i%j==0) {\n                       mp[j].insert(n);\n                       i=i/j;\n                   }\n               }\n\n               if (i>1) {\n                   mp[i].insert(n);\n               }\n        }\n     dsu mydsu(mx+1);\n        for (auto &i:mp) {\n             int fr=  *((i.second).begin());\n            for (auto &num:i.second) {\n                mydsu._union(fr,num);\n         \n            }\n        }\n\n        int ans=1;\n        for (int i=0;i<(mx+1);i++) {\n            ans=max(ans , mydsu.size[i]);\n        }\n        return ans;\n\n\n    }\n};\n```
['Union Find', 'Graph', 'C++']