[Cpp] Union-find using Map with explanation
tldr: By using map we can save the space from max(array) to sqrt(max(array)).\n\nThis question is basically asking the largest connected component in a forest. 
tldr: By using map we can save the space from max(array) to sqrt(max(array)).\n\nThis question is basically asking the largest connected component in a forest. In order to do so, we need to find a way to "group" all the nodes whose common divisor (one by one, not among any two) is greater than 1 together to a single tree, and we need a "root" as an id to quantify how many kids does this tree hold. This leads to Union-Find.\n\n---\nstep 1 build the graph:\n* start with all the nodes themselves, they are "self-connected"\n---\nstep 2 find all the divisor of current node\n* after we put node value to the tree, we also need to group all the divisor >= 2 with current root node.\n* this can be done with sqrt(n) times, since any two divisor a * b < n, a has to be less than sqrt(n).\n---\nstep 3 check the root and do the counting\n* now we have built our tree, and we can easily find the root node (or id) for each node, we can just count the number of id and find the max.\n```cpp\nclass Solution {\npublic:\n    unordered_map<int, int> p;\n    \n    int find(int a) {\n        if (!p.count(a)) return p[a] = a;\n        if (p[a] == a) return a;\n        return p[a] = find(p[a]);\n    }\n    \n    int largestComponentSize(vector<int>& A) {\n        int n = A.size();\n        for (int a : A)\n            p[a] = a;\n        for (int a : A) \n            for (int i = 2; i <= sqrt(a); ++i)\n                if (a % i == 0) {\n                    p[find(a)] = p[find(i)];\n                    p[find(a)] = p[find(a / i)];\n                }\n        unordered_map<int, int> cnt;\n        int res = 1;\n        for (int a : A)\n            res = max(res, ++cnt[find(a)]);\n        return res;\n    }\n};\n```\n\nQ&A:\nwhy \n```cpp\nfor (int a : A) \n\tfor (int i = 2; i <= sqrt(a); ++i)\n\t\tif (a % i == 0) {\n\t\t\tp[find(a)] = p[find(i)];\n\t\t\tp[find(a)] = p[find(a / i)];\n\t\t}\n```\ninstead of\n```cpp\nfor (int a : A) \n\tfor (int i = 2; i <= sqrt(a); ++i) {\n\t\tint root = find(a);\n\t\tif (a % i == 0) {\n\t\t\tp[root] = p[find(i)];\n\t\t\tp[root] = p[find(a / i)];\n\t\t}\n\t}\n```\nBecause our root is going to change every time when the p map is updated.\n
[]