C++ 232ms, Union-Find Solution
reference\n### Intuition\n\n(1) Union each number with all its factor;\n(2) Count the most frequent parent.\n\n\n// W: the largest number\n// Time Complexity: O
[reference](https://www.youtube.com/watch?v=GTX0kw63Tn0)\n### Intuition\n\n(1) Union each number with all its factor;\n(2) Count the most frequent parent.\n\n```\n// W: the largest number\n// Time Complexity: O(n*sqrt(W))\n// Space Complexity: O(W)\n\nclass UnionFindSet {\npublic:\n    UnionFindSet(int n) : _parent(n) {\n        for (int i=0; i<n; i++) {\n            _parent[i] = i;\n        }\n    }\n    \n    void Union(int x, int y) {\n        _parent[Find(x)] = _parent[Find(y)];\n    }\n    \n    int Find(int x) {\n        if (_parent[x] != x) {\n            _parent[x] = Find(_parent[x]);\n        }\n        return _parent[x];\n    }\n    \nprivate:\n    vector<int> _parent;\n};\n\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& A) {\n        int n = *max_element(A.begin(), A.end());\n        UnionFindSet ufs(n+1);\n        for (int &a : A) {\n            for (int k = 2; k <= sqrt(a); k++) {\n                if (a % k == 0) {\n                    ufs.Union(a, k);\n                    ufs.Union(a, a / k);\n                }\n            }\n        }\n        \n        unordered_map<int, int> mp;\n        int ans = 1;\n        for (int &a : A) {\n            ans = max(ans, ++mp[ufs.Find(a)]);\n        }\n        return ans;\n    }\n};\n```
[]