Brute Force to Optimal | C++ (Simple to Understand)
1) Brute Force colution :\n\t\n \tFind the greatest common divisors between two values.\n \tIf GCD is greater than 1, then merge it \n* \tDo DFS for all unvisit
1) **Brute Force colution** :\n\t\n* \tFind the greatest common divisors between two values.\n* \tIf GCD is greater than 1, then merge it \n* \tDo DFS for all unvisited value, print the maximum count of component.\n```\nclass Solution {\n    private :\n    int findGCD(int a, int b)\n    {\n        if(a == 0)\n            return b;\n        \n        return findGCD(b%a, a);\n    }\n        \n    \n    bool isCommon(int u, int v)\n    {\n        // find gcd \n        int gcd = findGCD(u, v);\n        \n        // gcd should be > 1\n        return gcd > 1;\n    }\n    \n    void dfs(int u, vector<int> adj[], int &curCount, vector<bool> &vis)\n    {\n        curCount++;\n        \n        vis[u] = true;\n        \n        for(auto v : adj[u])\n        {\n            if(!vis[v])\n            {\n                dfs(v, adj, curCount, vis);\n            }\n        }\n    }\n    \npublic:\n    int largestComponentSize(vector<int>& nums) {\n        \n        int n = nums.size();\n        \n        vector<int> adj[n];\n        \n        for(int i = 0; i < n; i++)\n        {\n            for(int j = i + 1; j < n; j++)\n            {\n                // if both values have common value, then add it to adjacent\n                if(isCommon(nums[i], nums[j]))\n                {\n                    adj[i].push_back(j);\n                    adj[j].push_back(i);\n                }\n            }\n        }\n        \n        vector<bool> vis(n, false);\n        int maxi = 0;\n        \n        // do dfs to find size of each component and print the maxi\n        for(int i = 0; i < n; i++)\n        {\n           if(!vis[i])\n           {\n               int curCount = 0;\n               \n               dfs(i, adj, curCount, vis);\n               \n               maxi = max(maxi, curCount);\n           }\n        }\n        \n        return maxi;\n    }\n};\n```\n\n2) Optimal solution (using union-find algorithm)\n\n```\nclass DSU\n{\n    private:\n    vector<int> parent;\n    \n    public:\n    DSU(int n)\n    {\n        for(int i = 0; i < n; i++)\n        {\n            parent.push_back(i);\n        }\n    }\n    \n    int findParent(int node)\n    {\n        if(parent[node] == node)\n            return node;\n        \n        return parent[node] = findParent(parent[node]);\n    }\n    \n    void _union(int u, int v)\n    {\n        int uParent = findParent(u);\n        int vParent = findParent(v);\n        \n        if(uParent != vParent)\n            parent[uParent] = parent[vParent];\n    }\n};\n\nclass Solution {\n  \npublic:\n    int largestComponentSize(vector<int>& nums) {\n        \n        int n = *max_element(nums.begin(), nums.end());\n         \n        DSU dsu(n+1);\n        \n        // do union for each element with all of the element\'s factors\n        for(auto &val : nums)\n        {\n            for(int i = 2; i * i <= val; i++)\n            {\n                if(val % i == 0)\n                {\n                    dsu._union(val, i);\n                    dsu._union(val, val/i);\n                    \n                }\n            }\n        }\n        \n        \n        unordered_map<int,int> mp;\n        int res = 1;\n        \n        // count the number of parent for each value\n        for(auto val : nums)\n        {\n            res = max(res, ++mp[dsu.findParent(val)]);\n        }\n        \n        return res;\n    }\n};\n```\n
['Union Find']