C++ | 232 ms | Union-find | Factorisation
Approach\n\nWe know from the problem statement, that if any two number have a common factor, they need to be put in the same set. For this, we can iterate over 
## Approach\n<hr>\nWe know from the problem statement, that if any two number have a common factor, they need to be put in the same set. For this, we can iterate over the list, factorize the number, for each of its factor (not 1 and number itself), we should unite the sets using [Disjoin set Union](https://cp-algorithms.com/data_structures/disjoint_set_union.html) (use path compession for efficiency).\n\nFor instance, if we have [4, 6]\n`factorize 4`: `2`\n`unite(4, 2)`\n`factorize 6`: `2, 3`\n`unite(6, 2)`\n`unite(6, 3)`\n\nat the end we see that 4 and 6 belong to the same set.\nwe use `unordered_map` to store parents and their frequency at the end and get parent with maximum size.\n\n## Code\n<hr>\n\n```cpp\nstruct DSU {\n\tvector<int> e;\n\tDSU(int N) { e = vector<int>(N, -1); }\n\tint get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }\n\tbool same_set(int a, int b) { return get(a) == get(b); }\n\tint size(int x) { return -e[get(x)]; }\n\tbool unite(int x, int y) { \n\t\tx = get(x), y = get(y);\n\t\tif (x == y) return false;\n\t\tif (e[x] > e[y]) swap(x, y);\n\t\te[x] += e[y]; e[y] = x;\n\t\treturn true;\n\t}\n};\n\nint largestComponentSize(vector<int>& nums) {\n\tDSU dsu(*max_element(nums.begin(), nums.end()) + 1); //create DSU struct with nodes 0, 1, 2, ... max element of the vector\n\tfor(auto i: nums){\n\t\tfor(int j = 2;j*j<=i;j++){ //factorize each number\n\t\t\tif(i%j == 0){\n\t\t\t\tdsu.unite(j, i);\n\t\t\t\tdsu.unite(i/j, i);\n\t\t\t}\n\t\t}\n\t}\n\tint ans = 1;\n\tunordered_map<int, int> freq;\n\tfor(auto i: nums){\n\t\tint p = dsu.get(i); //get parent\n\t\tfreq[p]++;\n\t\tans = max(ans, freq[p]);\n\t}\n\treturn ans;\n}\n```\n
[]