(C++) 952. Largest Component Size by Common Factor
\n\nclass UnionFind {\npublic: \n    vector<int> parent, rank; \n    UnionFind(int n) {\n        parent.resize(n); \n        iota(parent.begin(), parent.end(), 
\n```\nclass UnionFind {\npublic: \n    vector<int> parent, rank; \n    UnionFind(int n) {\n        parent.resize(n); \n        iota(parent.begin(), parent.end(), 0); \n        rank.resize(n); \n        fill(rank.begin(), rank.end(), 1); \n    }\n    \n    int find(int p) {\n        if (p != parent[p]) \n            parent[p] = find(parent[p]); \n        return parent[p]; \n    }\n    \n    bool connect(int p, int q) {\n        int prt = find(p), qrt = find(q); \n        if (prt == qrt) return false; \n        if (rank[prt] > rank[qrt]) swap(prt, qrt); \n        parent[prt] = qrt; \n        rank[qrt] += rank[prt]; \n        return true; \n    }\n}; \n\n\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        int m = *max_element(nums.begin(), nums.end()); \n        vector<bool> seen(m+1); \n        for (auto& x : nums) seen[x] = true; \n        UnionFind* uf = new UnionFind(m+1); \n        vector<bool> sieve(m+1, true); \n        sieve[0] = sieve[1] = false; \n        for (int x = 2; x <= m/2; ++x) \n            if (sieve[x]) {\n                int prev = seen[x] ? x : 0; \n                for (int xx = 2*x; xx <= m; xx += x) {\n                    sieve[xx] = false; \n                    if (seen[xx]) \n                        if (prev) uf->connect(prev, xx); \n                        else prev = xx; \n                }\n            }\n        int ans = *max_element(uf->rank.begin(), uf->rank.end()); \n        delete uf; \n        return ans; \n    }\n};\n```
['C']