Easy DSU solution || Beats 93.32% users
Intuition\n Describe your first thoughts on how to solve this problem. \n    Using DSU to achieve the graph quickly...\n# Approach\n Describe your approach to s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n    Using DSU to achieve the graph quickly...\n# Approach\n<!-- Describe your approach to solving the problem. -->\n    Implementing DSU and inserting every factor under same parent which \n    makes it easy to group element together \n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n    O(n * sqrt(max(nums)) * \u03B1(n))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n    O(n)\n# Code\n```\n#define inc()                                                                  \\\n    ios_base::sync_with_stdio(0);                                              \\\n    cin.tie(0);                                                                \\\n    cout.tie(0)\n\nclass DSU {\npublic:\n    vector<int> rank, parent;\n\n    DSU(int n) {\n        rank.resize(n, 0);\n        parent.resize(n, 0);\n        iota(parent.begin(), parent.end(), 0);\n    }\n\n    int find(int x) {\n        if (x == parent[x])\n            return x;\n\n        return parent[x] = find(parent[x]);\n    }\n\n    void UnionByRank(int x, int y) {\n        int x_parent = find(x);\n        int y_parent = find(y);\n\n        if (x_parent == y_parent)\n            return;\n\n        if (rank[x_parent] > rank[y_parent]) {\n            parent[y_parent] = x_parent;\n        } else if (rank[y_parent] > rank[x_parent]) {\n            parent[x_parent] = y_parent;\n        } else {\n            parent[x_parent] = y_parent;\n            rank[y_parent]++;\n        }\n    }\n};\n\nclass Solution {\npublic:\n    int largestComponentSize(vector<int>& nums) {\n        inc();\n\n        int n = *max_element(nums.begin(), nums.end()) + 1;\n        DSU dsu(n);\n\n        for (int& val : nums) {\n            for (int i = 2; i * i <= val; i++) {\n\n                if (val % i == 0) {\n                    dsu.UnionByRank(i, val);\n                    dsu.UnionByRank(val, val / i);\n                }\n                \n            }\n        }\n\n        int result = 0;\n        unordered_map<int, int> mp;\n\n        for (int& val : nums) {\n            int parent = dsu.find(val);\n            mp[parent]++;\n            result = max(result, mp[parent]);\n        }\n\n        return result;\n    }\n};\n```
['Union Find', 'C++']