[C++] Union-find
Approach 1: Union-find\n\nclass DSU {\npublic:\n  DSU(int n): p_(n) {\n    for (int i = 0; i < n; ++i)\n      p_[i] = i;\n  }\n  \n  void Union(int x, int y) {\
Approach 1: Union-find\n```\nclass DSU {\npublic:\n  DSU(int n): p_(n) {\n    for (int i = 0; i < n; ++i)\n      p_[i] = i;\n  }\n  \n  void Union(int x, int y) {\n    p_[Find(x)] = p_[Find(y)];\n  }\n  \n  int Find(int x) {\n    if (p_[x] != x) p_[x] = Find(p_[x]);\n    return p_[x];\n  }\nprivate:\n  vector<int> p_;\n};\n \nclass Solution {\npublic:\n  int largestComponentSize(vector<int>& A) {    \n    int n = *max_element(begin(A), end(A));\n    DSU dsu(n + 1);\n    for (int a : A) {\n      int t = sqrt(a);\n      for (int k = 2; k <= t; ++k)\n        if (a % k == 0) {\n          dsu.Union(a, k);\n          dsu.Union(a, a / k);\n        }\n    }\n    unordered_map<int, int> c;\n    int ans = 1;\n    for (int a : A)\n      ans = max(ans, ++c[dsu.Find(a)]);    \n    return ans;\n  }\n};\n```
['Union Find', 'C']