https://leetcode.com/problems/largest-component-size-by-common-factor

largest_component_size_by_common_factor.cpp

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    vector<int> primes;
    unordered_map<int, vector<int>> factors;
    unordered_map<int, vector<size_t>> revFactors;
    
    void computePrimes(int max) {
        // Assuming max is positive
        vector<bool> sieve(max + 1);
        
        for (int i = 2; i * i <= max; i++) {
            if (sieve[i]) {
                continue;
            }
            for (int j = i * i; j <= max; j += i) {
                sieve[j] = true;
            }
        }
        for (int i = 2; i <= max; i++) {
            if (!sieve[i]) {
                primes.push_back(i);
            }
        }
    }
        
    int dfs(int u, const vector<vector<int>>& graph, vector<bool>& visited) {
        visited[u] = true;
        int nodes = 1;
        for (int v : graph[u]) {
            if (visited[v]) {
                continue;
            }
            nodes += dfs(v, graph, visited);
        }
        return nodes;
    }
public:
    int largestComponentSize(vector<int>& A) {
        const int max = 100'001;
        computePrimes(sqrt(max));
        for (int p : primes) {
            for (int n = p; n < max; n += p) {
                factors[n].push_back(p);
            }
        }
        for (size_t i = 0; i < A.size(); i++) {
            for (auto factor : factors[A[i]]) {
                revFactors[factor].push_back(i);
            }
        }
        vector<vector<int>> graph(max);
        for (size_t u = 0; u < A.size(); u++) {
            for (auto factor : factors[A[u]]) {
                for (auto v : revFactors[factor]) {
                    if (v == u) {
                        continue;
                    }
                    graph[u].push_back(v);
                }
            }
        }


        vector<bool> visited(A.size());
        int answer = 0;
        for (size_t u = 0; u < A.size(); u++) {
            if (visited[u]) {
                continue;
            }
            answer = std::max(answer, dfs(u, graph, visited));
        }
        return answer;
    }
};