[C++] | Sieve of Eratosthenes | Normal DFS | Without DSU
class Solution {\npublic:\n\n\n    vector> g; // graph\n    vector isPrime, inArr,vis; // inArr[i] = 1, if i is present in nums\n    int cnt;\n    \n    void df
class Solution {\npublic:\n\n\n    vector<vector<int>> g; // graph\n    vector<int> isPrime, inArr,vis; // inArr[i] = 1, if i is present in nums\n    int cnt;\n    \n    void dfs(int node){\n        vis[node] = 1;\n        if(inArr[node]) cnt++; // count only if element (here node) is present in nums\n        for(auto &v: g[node]){\n            if(!vis[v]){\n                dfs(v);\n            }\n        }\n    }\n    \n    void sieve(int n){ // normal sieve\n        isPrime.assign(n+1,1);\n        isPrime[0] = isPrime[1] = 0;\n        for(int i = 2; i*i <= n; i++){\n            if(isPrime[i]){\n                for(long long j = i*i; j <= sqrt(n); j += i){\n                    isPrime[j] = 0;\n                }\n            }\n        }\n    }\n\n    int largestComponentSize(vector<int>& nums) {\n\t\n        int maxVal = -1;\n        for(auto &x: nums) maxVal = max(maxVal,x); // maxvalue in nums\n        sieve(maxVal+1);\n\t\tg.resize(maxVal+1); \n        inArr.assign(maxVal+1,0); vis.assign(maxVal+1,0);\n        \n        for(auto &x: nums) inArr[x] = 1;\n        // creating graph\n        for(int i = 1; i <= maxVal; i++){\n            if(isPrime[i]){    // connecting nums[i] with its primes\n                for(long long j = i*2; j <= maxVal; j += i){\n                    if(inArr[j]){\n                        g[i].push_back(j);\n                        g[j].push_back(i);\n                    }\n                }\n            }\n        }\n        \n        int ans = -1; \n        for(auto &x: nums){\n            if(!vis[x]){\n                cnt = 0;\n                dfs(x);\n                ans = max(ans,cnt); // counting size of maximum sized component\n            }\n        }\n        \n        return ans;\n    }\n};\n\n\nThis method extends the idea of sieve, here the elements of nums are connected with their prime factors and size of connected component is calculated for only those which are present in nums.\n\nExample: [4, 6, 15, 35]\n\n2: its prime: connect 2 and its multiples (which are present in nums) with it (here 4 and 6)\n3: its prime: connect 3 and its multiples (which are present in nums) with it (here 6 and 15)\n5: its prime: connect 5 and its multiples (which are present in nums) with it (here 15 and 35)\n7: its prime: connect 7 and its multiples (which are present in nums) with it (here 35 only)\n\nFinal graph will look like\n\n2 -- 4 -- 6 -- 3 -- 15 -- 5 -- 35 -- 7 (or print g for adjacency list view)\n\nCount elements which are present in nums to find the maximum size of connected component.
[]