Simplest Solution | Easy To Understand
\nclass Solution {\npublic:\n    \n    // M = MAX ELEMENT\n    // TIME COMPLEXITY:- O(MLOG(M))\n    // SPQACE COMPLEXITY:- O(M)\n    \n     // finds the parent 
```\nclass Solution {\npublic:\n    \n    // M = MAX ELEMENT\n    // TIME COMPLEXITY:- O(MLOG(M))\n    // SPQACE COMPLEXITY:- O(M)\n    \n     // finds the parent of a connected component\n    int find_set(int x,vector<pair<int,int>>& parent){\n        return parent[x].first==x?x:parent[x].first = find_set(parent[x].first,parent);\n    }\n    \n    // unites two connected component if they have different parent\'s\n    void union_set(int x,int y,vector<pair<int,int>>& parent,vector<int>& comp){\n        int xroot = find_set(x,parent),yroot = find_set(y,parent);\n        if(xroot==yroot)\n            return; // have same parent\n        \n        // rank compression \n        if(parent[xroot].second==parent[yroot].second)\n            parent[xroot].second++;\n        if(parent[xroot].second>parent[yroot].second){\n            parent[yroot].first = xroot;\n            comp[xroot] += comp[yroot]; // increase the component size on merging\n        }\n        else{\n            parent[xroot].first = yroot;\n            comp[yroot] += comp[xroot]; // increase the component size on merging\n        }\n    }\n    \n    int largestComponentSize(vector<int>& nums) {\n        int N = *max_element(nums.begin(),nums.end());\n        vector<bool> isPresent(N+1,false);\n        \n        for(auto& c:nums)\n            isPresent[c] = true;\n        \n        // use NlogN time to mark all numbers which have same factor i\n        vector<int> adj[N+1];\n        for(int i=2;i<=N;i++){\n            for(int j=i;j<=N;j+=i){\n                if(isPresent[j])\n                    adj[i].push_back(j);\n            }\n        }\n        \n        // parent[i].first = store parent of the connected component\n        // parent[i].second = store rank of the connected component\n        // comp[i] will store size of connected component\n        \n        vector<int> comp(N+1);\n        vector<pair<int,int>> parent;\n        for(int i=0;i<=N;i++){\n            if(isPresent[i])\n                comp[i] = 1;\n            parent.push_back({i,0});\n        }\n        \n        // unite two numbers which has same factor i\n        for(int i=1;i<=N;i++){\n            for(int j=1;j<adj[i].size();j++)\n                union_set(adj[i][j-1],adj[i][j],parent,comp);\n        }\n        \n        // find the maximum size of connected component\n        int ans = 0;\n        for(auto& c:comp)\n            ans = max(ans,c);\n        \n        return ans;\n    }\n};\n```
[]