<p>You are given an integer array of unique positive integers <code>nums</code>. Consider the following graph:</p>

<ul>
	<li>There are <code>nums.length</code> nodes, labeled <code>nums[0]</code> to <code>nums[nums.length - 1]</code>,</li>
	<li>There is an undirected edge between <code>nums[i]</code> and <code>nums[j]</code> if <code>nums[i]</code> and <code>nums[j]</code> share a common factor greater than <code>1</code>.</li>
</ul>

<p>Return <em>the size of the largest connected component in the graph</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex1.png" style="width: 500px; height: 97px;" />
<pre>
<strong>Input:</strong> nums = [4,6,15,35]
<strong>Output:</strong> 4
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex2.png" style="width: 500px; height: 85px;" />
<pre>
<strong>Input:</strong> nums = [20,50,9,63]
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2018/12/01/ex3.png" style="width: 500px; height: 260px;" />
<pre>
<strong>Input:</strong> nums = [2,3,6,7,4,12,21,39]
<strong>Output:</strong> 8
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
	<li>All the values of <code>nums</code> are <strong>unique</strong>.</li>
</ul>

class dsu{
    public:
    vector<int> par, rank;

    dsu(int n){
        par.resize(n+1);
        rank.resize(n+1);

        for(int i=0; i<=n; i++){
            par[i] = i;
            rank[i] = 1;
        }
    }

    int findParent(int u){
        if(par[u] == u) return u;

        return findParent(par[u]);
    }

    void Union(int u, int v){
        int pu = findParent(u), pv = findParent(v);

        if(pu == pv) return;

        if(rank[pu] > rank[pv]){
            par[pv] = pu;
            rank[pu]++;
        } else {
            par[pu] = pv;
            rank[pv]++;
        }

        return;
    }
};

class Solution {
public:
    vector<bool> primes;
    void sieve(){
        primes.resize(1e5+1, true);

        for(int p=2; p<=1e5; p++){
            if(primes[p] == false) continue;

            //mp[p] = 1;

            for(int j=2*p; j<=1e5; j+=p){
                primes[j] = false;
            }
        }
    }

    vector<int> primeDivisors(int x){
        if(primes[x]) return {x};

        vector<int> s;

        for(int p=2; p*p <= x; p++){
            if(x%p == 0){
                if(primes[p]) s.push_back(p);

                if(primes[x/p]) s.push_back(x/p);
            }
        }

        return s;
    }

    int largestComponentSize(vector<int>& nums) {
        sieve();

        int n = nums.size();

        dsu ds(n+1);

        map<int, int> mp; 
        
        for(int i=0; i<n; i++){
            vector<int> v = primeDivisors(nums[i]);

            for(int j=0; j<v.size(); j++){
                if(mp[v[j]]){
                    ds.Union(i+1, mp[v[j]]);
                }
                else mp[v[j]] = i+1;
            }
        }

        map<int, int> count;

        for(int p=1; p<=n; p++){
            int pu = ds.findParent(p);
            count[pu]++;
        }

        int sz = 0;
        for(auto it: count){
            sz = max(sz, it.second);
        }

        return sz;
    }
};
74573