C++ Brute to Optimal solution
Method 1\n\nFrom question it can be clearly observed that two numbers have an edge if their gcd is >1. Using this we can try to construct the graph and then per
## Method 1\n\nFrom question it can be clearly observed that two numbers have an edge if their gcd is >1. Using this we can try to construct the graph and then perform dfs/bfs to find largest connected component.\n\n### Code\n```\nclass Solution {\n    \n    void recur(int node,unordered_map<int,vector<int>> &mp,unordered_map<int,bool> &vis)\n    {\n        vis[node] = 1;\n        // int cnt = 0;\n        for(auto &val : mp[node])\n        {\n            if(vis.find(val) == vis.end())\n            {\n                recur(val,mp,vis);\n            }\n        }\n    }\n    \n    int dfs(unordered_map<int,vector<int>> &mp)\n    {\n        int res = 0,prev = 0;\n        unordered_map<int,bool> vis;\n        for(auto &[key,value] : mp)\n        {\n            if(vis.find(key) == vis.end())\n            {\n                recur(key,mp,vis);\n            }\n            \n            int len = vis.size() - prev;\n            res = max(len,res);\n            prev = vis.size();\n        }\n        \n        return res;\n    }\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        unordered_map<int,vector<int>> mp;\n        for(int i=0;i<nums.size();i++)\n        {\n            for(int j=i+1;j<nums.size();j++)\n            {\n                if(__gcd(nums[i] , nums[j]) > 1)\n                {\n                    mp[nums[i]].push_back(nums[j]);\n                    mp[nums[j]].push_back(nums[i]);\n                }\n            }\n        }\n        \n        return dfs(mp);\n    }\n};\n```\n\n**Time Complexity :**  O(n^2 * logn)\n**Space Complexity :** O(n) [for map]\n\n## Method 2\n\nSince we only need connected components so instead of creating the whole graph , we can use something called Disjoint Set Union.\n\n### Code\n\n```\nclass Solution {\n    map<int,int> rank;\n    map<int,int> par;\n    \n    void init(vector<int> &nums)\n    {\n        for(auto &val : nums) rank[val] = 1 , par[val] = val;\n    }\n    \n    int findPar(int u)\n    {\n        if(par[u] == u) return u;\n        \n        return par[u] = findPar(par[u]);\n    }\n    \n    void unn(int u,int v)\n    {\n        int x = findPar(u) , y = findPar(v);\n        if(rank[x] > rank[y]) par[y] = x;\n        else if(rank[x] < rank[y]) par[x] = y;\n        else par[x] = y , rank[y]++;\n    }\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        init(nums);\n        for(int i=0;i<nums.size();i++)\n        {\n            for(int j=i+1;j<nums.size();j++)\n            {\n                if(__gcd(nums[i],nums[j]) > 1)\n                {\n                    unn(nums[i],nums[j]);\n                }\n            }\n        }\n        \n        unordered_map<int,int> mp;\n        for(auto &val : nums) mp[findPar(val)]++;\n        \n        int res = 0, len = 0;\n        \n        for(auto &[key,value] : mp)\n        {\n            if(value > len) len = value;\n        }\n        \n        return len;\n        \n    }\n};\n```\n\n**Time Complexity :** O(n^2)\n**Space Complexity :** O(n) [for rank and par map]\n\n## Method 3 (Optimal)\n\nWe know that elements having same factors can be put in one set. So we\'ll calculate factors of every element in nums and then put elements with same factor in same set.\n\n```\nclass Solution {\n    void init(vector<int> &par)\n    {\n        for(int i=0;i<=100001;i++)\n            par.push_back(i);\n    }\n    \n    int findPar(int u,vector<int> &par)\n    {\n        if(par[u] == u) return u;\n        \n        return par[u] = findPar(par[u],par);\n    }\n    \n    void unn(int u,int v,vector<int> &par)\n    {\n        int x = findPar(u,par) , y = findPar(v,par);\n        if(x != y) par[x] = y;\n    }\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        vector<int> par;\n        init(par);\n        \n        for(auto &val : nums)\n        {\n            for(int k=2;k<=sqrt(val);k++)\n            {\n                if(val%k == 0)\n                {\n                    unn(val,k,par);\n                    unn(val,val/k,par);\n                }\n            }\n        }\n        \n        int cnt = 0;\n        unordered_map<int,int> mp;\n        \n        for(auto &val : nums)\n        {\n            int x = findPar(val,par);\n            mp[x]++;\n            cnt = max(cnt,mp[x]);\n        }\n        \n        return cnt;\n    }\n};\n```\n\n**Time Complexity :** O(n * sqrt(max element in nums))\n**Space Complexity :** O(n) [for parent array]\n
['Union Find']