C++ and Python | Explained | 2 solutions based on Sieve | O(n*log(m)); O(m)
I suggest reading this post only after you understood the O(n*sqrt(m))solution.\n\nIn this problem we need to find the largest component where the numbers share
I suggest reading this post only after you understood the `O(n*sqrt(m)) `solution.\n\nIn this problem we need to find the largest component where the numbers share a common factor.\nFor this let us create these components, and then simply find the one which has more numbers.\n\n1. How can we create the components?\n The main idea is to use prime factor decomposition (i.e. 42 = 2 * 3 * 7). Let us build a dictionary (unordered_map) with keys - prime numbers, and values - the numbers which have this prime in their decomposition.\n 2. Why do we build this dictionary?\n Because we need to connect the numbers fast. If we know that 3 numbers (let them be 2, 6, 8) have 2 as their common factor, then we know that 2, 6 and 8 are in the same component.\n 3. How can we decompose our numbers?\n There are 2 approaches with time complexities `O(sqrt(k))` and `O(log(k))` for each number k. The latter one is faster but it requires more space, we will use this one. There we should build a specific Sieve. In the `O(sqrt(k))` approach we go through each number `i = 1...sqrt(k)`, and check if `k mod i = 0` (i.e. we find the smallest prime factor which divides our number k). Now, what if we know already for every number k which is its smallest prime factor? Then, we can find its decomposition by dividing the given number recursively with its smallest prime factor till it becomes 1. Take 12, you divide it by 2 (you get 6), then one more time by 2 (you get 3), and then divide by 3 (you get 1, you stop the process, and you know that 12 = 2 * 2 * 3). In the original Sieve we have `Sieve[i] = true` if `i - prime`, else false. In our Sieve, which we will call \'spf\' (smallest prime factor), `spf[i] = i` if `i - prime`, and each time we get a prime number, we make `spf[2i], spf[3i], spf[4i] ... = i`. Also we should check if \'i\' isn\'t already a smallest prime factor of another number. \n 4. What\'s next?\n Now, we know how to create components for every unique prime, however there is a problem, we still need to connect the components which share at least one number. For example if we have 3 numbers (let them be 3, 5, 15), we will have 2 components (the former for the prime 3 (3, 15), and the latter for the prime 5 (5, 15)) but for this problem 3, 5 and 15 should be in the same component.\n 5. How can we fix that?\n I will show 2 solutions, one in C++ with DSU (Disjoint Set Union) - `O(n*logn)`, and another in Python with BFS - `O(n)`\n \n**C++ with DSU**\n1. We build the Sieve and the primes dictionary.\n2. We create the DSU, and then we join the numbers which share the same factor.\n3. We count how many elements we have in each component and return the largest one.\n```\nclass Solution { // Sieve + DSU\npublic:\n    vector<int> parent, spf;\n    void sieve(int N, vector<int> &spf) {\n        spf = vector<int> (N);           // N = max(A) + 1\n        for(int i = 1; i < N; ++i)       // Initially, we mark smallest prime factor for every number to be itself. \n            spf[i] = i;\n        for(int i = 2; i < N; i += 2)    // Like in the Sieve, it\'s easier to mark even numbers separately \n            spf[i] = 2;\n        for(int i = 3; i < N; i += 2)\n            if (spf[i] == i)             // If spf[i] == i, our number is prime\n                for(int j = i; j < N; j += i)\n                    if (spf[j] == j)     // Before we mark each 2i, 3i, 4i ..., we should check if it wasn\'t already marked. Take 6, it is marked by 2 but it can also be marked by 3.\n                        spf[j] = i;\n    }\n    int find(int node) {\n        return node == parent[node] ? parent[node] : parent[node] = find(parent[node]);   \n    }\n    int largestComponentSize(vector<int>& A) {\n        sieve(*max_element(A.begin(), A.end()) + 1, spf); // 1\n        unordered_map <int, unordered_set<int>> primes;\n        for(int i = 0; i < A.size(); ++i) {\n            int num = A[i];\n            while(num != 1) {\n                primes[spf[num]].insert(i);\n                num /= spf[num]; \n            }\n        }\n        \n        parent = vector<int> (A.size()); // 2\n        for(int i = 0; i < A.size(); ++i)\n            parent[i] = i;\n        for(auto [_, x]: primes) {\n            int i = *x.begin();\n            x.erase(x.begin());\n            for(int j: x)\n                parent[find(i)] = find(j);\n        }\n        \n        vector<int> components(A.size()); // 3\n        for(int x: parent)\n            components[find(x)]++;\n        return *max_element(components.begin(), components.end());\n    }\n};\n```\n\n**Python with BFS**\n1. We build the Sieve and the primes dictionary.\n2. For each number that we haven\'t visited yet, we run a BFS over the primes in its decomposition.\n3. For each prime, we find other numbers which have this prime in their decomposition, and we increment the number of components in our current (\'cur\') component. Also, we add to our queue other factors which we haven\'t visited.\n```\nclass Solution:  # Sieve + BFS \n    \n    def largestComponentSize(self, A: List[int]) -> int:\n        \n        def sieve():\n            i = 2\n            while i < len(spf):\n                spf[i] = 2\n                i += 2\n            i = 3\n            while i * i < len(spf):\n                if spf[i] == i:\n                    j = i\n                    while j < len(spf):\n                        if spf[j] == j:\n                            spf[j] = i\n                        j += i\n                i += 2\n        \n        spf, di, factors, visited_nums, visited_factors, ans = [i for i in range(max(A) + 1)], defaultdict(set), defaultdict(set), set(), set(), 1\n        \n        sieve()  # 1\n        \n        for num in A:\n            x = num\n            while x != 1:\n                di[spf[x]].add(num)\n                factors[num].add(spf[x])\n                x //= spf[x]\n        \n        for num in A:  # 2\n            if num in visited_nums:\n                continue\n                \n            visited_nums.add(num)\n            cur, queue = 1, deque([])\n            for factor in factors[num]:\n                queue.append(factor)\n                \n            while queue: \n                factor = queue.popleft()\n                visited_factors.add(factor)\n                for next_num in di[factor]:  # 3\n                    if next_num in visited_nums:\n                        continue\n                        \n                    visited_nums.add(next_num)\n                    cur += 1\n                    for next_factor in factors[next_num]:\n                        if next_factor in visited_factors:\n                            continue\n                        \n                        visited_factors.add(next_factor)\n                        queue.append(next_factor)\n                \n            ans = max(ans, cur)\n        \n        return ans\n        \n        \n            \n```\n\nEven if the DSU is slower than the BFS, the time complexities of both solutions are the same due to the Sieve.\n\n`TC - O(n*log(m))`, where m is the biggest number in our array\n`SC - O(m)`
[]