✅ [C++] 3 Simple Solution w/ Explanation | Disjoint Set Union + Sieve of Eratosthenes
We are given an array nums each element of which denotes a node in the graph. There is an edge between two elements if they share a common factor. We need to re
We are given an array `nums` each element of which denotes a node in the graph. There is an edge between two elements if they share a common factor. We need to return the largest connected component in this graph.\n\n\n---\n\n\u2714\uFE0F ***Solution - I (Union-Find)***\n\nThe problem statement can be stated in simpler terms as - two element belong to same group if they share a common factor. We need to find largest of such groups. \n\nFor eg. If we have numbers `[2,3,5,6,25]`, then we can see `2` & `6` share a common factor. So lets say they belong to group `A`. `3` & `6` also share a common factor, so 3 belongs to group `A` as well. `5` and `25` is another pair sharing a common factor so they belong to one group, lets say `B`. So, out of all these groups, `A` is the largest and it will be our answer.\n\nThere\'s a common Data Structure that can be used in such problems - **[Disjoint Set Union](https://en.wikipedia.org/wiki/Disjoint-set_data_structure)**. \n\n<blockquote>\n<details>\n<summary><b>Brief Description of DSU</b></summary>\n\nDisjoin Set Union or DSU involes two basic operations -\n* **`find(x)`**: finds the id which represents the component that a node belongs to\n* **`union(x, y)`**: joins the two components into a single component. This involves finding the representative of x-component (by `find(x)`) and y-component (by `find(y)`) and assigning them a common  representative (same parent).\n\nIn simple implementation, we can only maintain a `par` array denoting parent of each node and define a `find` function that finds representative/parent of component that a given node belongs to. In more optimized versions, we use path compression in `find` function along with either use a rank or size to group elements based on their component rank/size to ensure that even in the worst case, DSU doesnt form a skewed tree. You can read on more about it **[here](https://cp-algorithms.com/data_structures/disjoint_set_union.html)**\n\n</details>\n</blockquote>\n\nHere, we use DSU to group elements of `nums` and its factors into a single component. Once this is done, all elements of `nums` that share a common factor will belong to the same component and will have the same parent in DSU. Then we can just iterate over `nums`, and find the parent of component that it belongs to. We keep count of number of times that each parent is seen. The largest group will be the one whose parent is seen maximum number of times.\n\nWe can find the factors of a number in `O(sqrt(N))` time and union each factor with that number itself.\n\n```cpp\n// a standard Disjoint Set Union class template\nclass DSU {\n    public:\n    vector<int> par, sz;\n    DSU(int n) : par(n), sz(n,1) {\n        iota(begin(par), end(par), 0);                         // initializes each node\'s parent to be itself - fills as [0,1,2,3,...,n]\n    }\n    int find(int x) {\n        if(par[x] == x) return x;                              // x is itself the parent of the component that it belongs to\n        return par[x] = find(par[x]);                          // update parent of x before returning for each call -path compression\n    }\n    bool Union(int x, int y) {\n        int xp = find(x), yp = find(y);                        // find parents of x and y, i.e, representatives of components that x and y belong to\n        if(xp == yp) return false;                             // x and y already belong to same component - not possible to union\n        if(sz[xp] > sz[yp]) par[yp] = par[xp], sz[xp] += sz[yp];   // union by size - join smaller sized to bigger one\n        else par[xp] = par[yp], sz[yp] += sz[xp];\n        return true;\n    }\n};\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        int n = size(nums), ans = 1;\n        DSU ds(*max_element(begin(nums), end(nums)) + 1);      // max(nums) is largest element that will be stored in DSU\n        unordered_map<int, int> mp;                            // maintains {parent of component: frequency}\n        for(auto c : nums) \n            for(int f = 2; f <= sqrt(c); f++)                  // finding factors of each element\n                if(c % f == 0)                                 // if f divides c, then f & c/f are its factor. So union them\n                    ds.Union(c, f), \n                    ds.Union(c, c/f);\n        \n        for(int i = 0; i < n; i++)                             // iterate and find parent that is seen most. It\'ll give the largest group\n            ans = max(ans, ++mp[ds.find(nums[i])]);\n        return ans;\n    }\n};\n```\n\n\n***Time Complexity :*** `O(N * sqrt(M))`, where `N` is the number of elements in `nums` and `M` is the maximum element in `nums`. The time complexity of each `find` call after union-by-size and path compression comes out to be `O(\u03B1(n))`, where `\u03B1(n)` is the inverse Ackermann function. It doesn\'t exceed 4 for any <code>n < 10<sup>600</sup></code> and hence is practically constant. We take each `N` elements from `nums` and iterate upto `sqrt(num[i])`. Thus the overall time comes out to `O(N * sqrt(M))`.\n***Space Complexity :*** `O(M)`, for DSU\n\n---\n\n\u2714\uFE0F ***Solution - II (Union-Find w/ Prime Factorization)***\n\nWe can see that if two numbers belong to the same group due to some common factor, they should also have some common prime factor. This allows us to use slightly different approach where we find all prime factors of a number and union the elements based on the common prime factors amongst them. This can reduce the space used by DSU to `O(N)` down from `O(M)` by allowing us to perform union on indices of elements instead of elements & its factors, although we do incur a cost of storing primes and elements in `nums` that it divides.\n\n```cpp\nclass UnionFind {\n    public:\n    vector<int> par, sz;\n    UnionFind(int n) : par(n), sz(n,1) {\n        iota(begin(par), end(par), 0);\n    }\n    int find(int x) {\n        if(par[x] == x) return x;\n        return par[x] = find(par[x]);\n    }\n    bool Union(int x, int y) {\n        int xp = find(x), yp = find(y);\n        if(xp == yp) return false;\n        if(sz[xp] > sz[yp]) par[yp] = par[xp], sz[xp] += sz[yp];\n        else par[xp] = par[yp], sz[yp] += sz[xp];\n        return true;\n    }\n};\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        int n = size(nums), ans = 1;\n        UnionFind uf(n + 1);\n        unordered_map<int, vector<int>> mp;             // stores {p : [indices of nums for which p is prime factor]}\n        for(int i = 0; i < n; i++) {                    // prime factorize nums[i]\n            int cur = nums[i];\n            if(cur % 2 == 0) {                          // 2 is prime factor of nums[i]\n                mp[2].push_back(i);\n                while(cur % 2 == 0) cur >>= 1;\n            }\n            for(int p = 3; p <= sqrt(cur); p += 2)      // now check for all odd numbers if it is factor of nums[i]\n                if(cur % p == 0) {                      // p is prime factor of nums[i]\n                    mp[p].push_back(i);\n                    while(cur % p == 0) cur /= p;\n                }\n            \n            if(cur > 1) mp[cur].push_back(i);           // nums[i] itself is prime\n        }\n        \n        for(auto& [prime, ids] : mp)                    // union all element index that have same prime\n            for(int i = 0; i < size(ids)-1; i++) \n                uf.Union(ids[i], ids[i+1]);\n        \n        return *max_element(begin(uf.sz), end(uf.sz));  // return largest component\n    }\n};\n```\n\nHowever, we can add another small optimization for space. Instead of storing all the primes as a vector in the hashmap and then performing union on the indices of element that each prime divides, we can just put the 1st index of element we find that a prime `p` divides and then for every subsequent indices, we just union them there itself. This saves space and also eliminate the last step of iterating over each prime and then unioning the indices. \n\nThe following code will make this optimization clear -\n\n```cpp\nclass UnionFind {\n    public:\n    vector<int> par, sz;\n    UnionFind(int n) : par(n), sz(n,1) {\n        iota(begin(par), end(par), 0);\n    }\n    int find(int x) {\n        if(par[x] == x) return x;\n        return par[x] = find(par[x]);\n    }\n    bool Union(int x, int y) {\n        int xp = find(x), yp = find(y);\n        if(xp == yp) return false;\n        if(sz[xp] > sz[yp]) par[yp] = par[xp], sz[xp] += sz[yp];\n        else par[xp] = par[yp], sz[yp] += sz[xp];\n        return true;\n    }\n};\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        int n = size(nums), ans = 1;\n        UnionFind uf(n + 1);\n        unordered_map<int, int> mp;                    // stores {p : 1st found index i such that nums[i] % p == 0}\n        auto putOrUnion = [&](int p, int i){           // puts 1st found index of element that p divides into hashmap\n            if(mp.count(p)) uf.Union(mp[p], i);        // and if already exists, directly union them\n            else mp[p] = i;\n        };\n        for(int i = 0; i < n; i++) {                   // prime factorize nums[i]\n            int cur = nums[i];\n            if(cur % 2 == 0) {                        \n                putOrUnion(2, i);\n                while(cur % 2 == 0) cur >>= 1;\n            }\n            for(int p = 3; p <= sqrt(cur); p += 2)   \n                if(cur % p == 0) {                 \n                    putOrUnion(p, i);\n                    while(cur % p == 0) cur /= p;\n                }\n            if(cur > 1) putOrUnion(cur, i);            // nums[i] itself is prime   \n        }\n        return *max_element(begin(uf.sz), end(uf.sz)); // return largest component\n    }\n};\n```\n\n***Time Complexity :*** `O(N * sqrt(M))` same as above\n***Space Complexity :*** \n* 1st Implementation: <code>O(N + \u2211\u03C9(nums<sub>i</sub>))</code> \n* 2nd Implementation: `O(N + \u03C0(M))`\n \nwhere `\u03C9(n)` is the **[prime omega function](https://en.wikipedia.org/wiki/Prime_omega_function)** and `\u03C0(n)` is the **[prime counting function](https://en.wikipedia.org/wiki/Prime-counting_function)** which is approximately equal to `O(n/logn)`. Let me know if there\'s a better way to describe the space complexity or if there\'s a mistake in this analysis.\n\n\n\n\n---\n\n\u2714\uFE0F ***Solution - III (Union-Find w/ Prime Factorization using Sieve of Eratosthenes)***\n\nWe can use sieve of Eratosthenes to compute prime factorization queries in better time complexity than O(sqrt(M)). The logic is similar to above but we have just changed the way we compute prime factors for each element in `nums`. \n\n<blockquote>\n<details>\n\n<summary>Similar to 1st implementation in <code>Solution - II</code></summary>\n\n```cpp\nclass UnionFind {\n    public:\n    vector<int> par, sz;\n    UnionFind(int n) : par(n), sz(n,1) {\n        iota(begin(par), end(par), 0);\n    }\n    int find(int x) {\n        if(par[x] == x) return x;\n        return par[x] = find(par[x]);\n    }\n    bool Union(int x, int y) {\n        int xp = find(x), yp = find(y);\n        if(xp == yp) return false;\n        if(sz[xp] > sz[yp]) par[yp] = par[xp], sz[xp] += sz[yp];\n        else par[xp] = par[yp], sz[yp] += sz[xp];\n        return true;\n    }\n};\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        int n = size(nums), M = *max_element(begin(nums), end(nums)), ans = 1;\n        auto spf = sieve(M+1);\n        UnionFind uf(n + 1);\n        unordered_map<int, vector<int>> mp;           // stores {p : [indices of nums for which p is prime factor]}\n        for(int i = 0; i < n; i++)                    // prime factorize nums[i]\n            for(auto p : getPrimes(nums[i], spf))\n                mp[p].push_back(i);\n        \n        for(auto& [prime, ids] : mp)                  // union all element index that have same prime\n            for(int i = 0; i < size(ids)-1; i++) \n                uf.Union(ids[i], ids[i+1]);\n        \n        return *max_element(begin(uf.sz), end(uf.sz));\n    }\n    \n    vector<int> sieve(int M) {\n        vector<int> spf(M+1);\n        iota(begin(spf), end(spf), 0);\n        for(int i = 2; i*i < M; i++) \n            if(spf[i] == i) \n                for(int j = i*i; j < M; j += i)\n                    if(spf[j] == j)\n                        spf[j] = i;            \n        return spf;\n    }\n\n    vector<int> getPrimes(int x, vector<int>& spf) {\n        vector<int> primes;\n        while (x != 1) {\n            int p = spf[x];\n            primes.push_back(p);\n            while(x % p == 0) x /= p;\n        }\n        return primes;\n    }\n};\n```\n\n***Time Complexity :*** `O((N+M)logM)`\n***Space Complexity :*** <code>O(M + \u2211\u03C9(nums<sub>i</sub>))</code>\n\n</details>\n</blockquote>\n\n```cpp\nclass UnionFind {\n    public:\n    vector<int> par, sz;\n    UnionFind(int n) : par(n), sz(n,1) {\n        iota(begin(par), end(par), 0);\n    }\n    int find(int x) {\n        if(par[x] == x) return x;\n        return par[x] = find(par[x]);\n    }\n    bool Union(int x, int y) {\n        int xp = find(x), yp = find(y);\n        if(xp == yp) return false;\n        if(sz[xp] > sz[yp]) par[yp] = par[xp], sz[xp] += sz[yp];\n        else par[xp] = par[yp], sz[yp] += sz[xp];\n        return true;\n    }\n};\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        int n = size(nums), ans = 1;\n        auto spf = sieve(*max_element(begin(nums), end(nums))+1);\n        UnionFind uf(n + 1);\n        unordered_map<int, int> mp;                      // stores {p : 1st found index i such that nums[i] % p == 0}\n        for(int i = 0; i < n; i++)                       // prime factorize nums[i]\n            for(auto p : getPrimes(nums[i], spf))\n                if(mp.count(p)) uf.Union(i, mp[p]);\n                else mp[p] = i;\n        \n        return *max_element(begin(uf.sz), end(uf.sz));\n    }\n    \n    vector<int> sieve(int M) {\n        vector<int> spf(M+1);\n        iota(begin(spf), end(spf), 0);\n        for(int i = 2; i*i < M; i++) \n            if(spf[i] == i) \n                for(int j = i*i; j < M; j += i)\n                    if(spf[j] == j)\n                        spf[j] = i;            \n        return spf;\n    }\n\n    vector<int> getPrimes(int x, vector<int>& spf) {\n        vector<int> primes;\n        while (x != 1) {\n            int p = spf[x];\n            primes.push_back(p);\n            while(x % p == 0) x /= p;\n        }\n        return primes;\n    }\n};\n```\n\n\n\n***Time Complexity :*** `O(M*log(logM) + N*logM)`, we require `O(M*log(logM))` time to initially compute the sieve.Then, every query to `getPrimes` will require `O(logM)` and this is queried for `N` times. So overall time complexity becomes `O(M*loglogM + NlogM)`.\n\n***Space Complexity :*** `O(M)`, for sieve\n\nYou can search **`sieve of eratosthenes GFG`** to read more about it on GFG from where this implementation is referred (unfortunately LC doesn\'t allow external links or even names of sites in post \u2639\uFE0F).\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---
[]