[C++] Union Find + Sieve
Interesting Union Find Problems: \n\n- 959. Regions Cut By Slashes [Medium] \n- 947. Most Stones Removed with Same Row or Column [Medium]\n- 990. Satisfiability
Interesting Union Find Problems: \n\n- [959. Regions Cut By Slashes](https://leetcode.com/problems/regions-cut-by-slashes/) [Medium] \n- [947. Most Stones Removed with Same Row or Column](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/) [Medium]\n- [990. Satisfiability of Equality Equations](https://leetcode.com/problems/satisfiability-of-equality-equations/) [Medium]\n- [952. Largest Component Size by Common Factor](https://leetcode.com/problems/largest-component-size-by-common-factor/) [Hard] - current question\n- [1627. Graph Connectivity With Threshold](https://leetcode.com/problems/graph-connectivity-with-threshold/) [Hard]\n- [1998. GCD Sort of an Array](https://leetcode.com/problems/gcd-sort-of-an-array/) [Hard]\n\n```\nclass UnionFind {\n    vector<int> parent, size;\npublic:\n    UnionFind(int n) {\n        parent.resize(n); size.resize(n);\n        for (int i = 0; i < n; i++) {\n            parent[i] = i, size[i] = 1;\n        }\n    }\n    \n    int Find(int x) {\n        if (x == parent[x]) return x;\n        return parent[x] = Find(parent[x]); // Path compression\n    }\n    \n    bool Union(int u, int v) {\n        int pu = Find(u), pv = Find(v);\n        if (pu == pv) return false; // Return False if u and v are already part of the same component\n        if (size[pu] > size[pv]) { // Union by larger size\n            size[pu] += size[pv];\n            parent[pv] = pu;\n        } else {\n            size[pv] += size[pu];\n            parent[pu] = pv;\n        }\n        return true;\n    }\n    \n    int getComponentSize(int x) {\n        return size[Find(x)];\n    }\n};\n\nclass Solution {\npublic:\n    vector<int> spf; // spf[x] is the smallest prime factor of number x, where x >= 2\n    \n    int largestComponentSize(vector<int>& nums) {\n        int maxNum = *max_element(nums.begin(), nums.end());\n        UnionFind uf(maxNum + 1);\n        sieve(maxNum);\n        \n        for (int x : nums) {\n            for (int pf : getPrimeFactors(x)) {\n                uf.Union(pf, x);\n            }\n        }\n        \n        int res = 1; // max_component_size\n        map<int, int> component_size;\n        for (int x : nums) {\n            int parent = uf.Find(x);\n            component_size[parent]++;\n            res = max(res, component_size[parent]);\n        }\n        \n        return res;\n    }\n    \n    void sieve(int n) {\n        spf.resize(n+1);\n        for (int i = 2; i <= n; ++i)\n            spf[i] = i;\n\n        for (int i = 2; i * i <= n; i++) {\n            if (spf[i] != i) continue; // skip if `i` is not a prime number\n            for (int j = 2*i; j <= n; j += i) {\n                if (spf[j] > i) { \n                    spf[j] = i;\n                }\n            }\n        }\n    }\n    \n    vector<int> getPrimeFactors(int n) { // O(logN)\n        vector<int> factors;\n        while (n > 1) {\n            factors.push_back(spf[n]);\n            int s = spf[n]; // smallest prime factor\n            while (n % s == 0) { n /= s;}\n        }\n        return factors;\n    }\n    \n};\n```\n\nReferences: \n- https://leetcode.com/problems/gcd-sort-of-an-array/discuss/1445180/C%2B%2BPython-Union-Find-and-Sieve-and-Sorting-Clean-and-Concise\n
[]