<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>

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

class UnionBySize
{
public:
    vector<int> parent;
    vector<int> size;
    UnionBySize(int n)
    {
        parent.resize(n, 0);
        for (int i = 0; i < n; ++i)
        {
            parent[i] = i;
        }
        size.resize(n, 0);
    }

    int find(int node)
    {
        if (parent[node] != node)
        {
            return parent[node] = find(parent[node]);
        }
        return parent[node];
    }

    void unionsets(int u, int v)
    {
        int uroot = find(u);
        int vroot = find(v);
        if (uroot != vroot)
        {
            if (size[uroot] > size[vroot])
            {
                parent[vroot] = uroot;
                size[uroot] += size[vroot];
            }
            else
            {
                parent[uroot] = vroot;
                size[vroot] += size[uroot];
            }
        }
    }

    int find_max_set()
    {
        return *max_element(size.begin(), size.end());
    }
};

class Solution
{
public:
    // write a function to find all the primes till 1e5
    map<int, vector<int>> mt;
    set<int> all;

    void find_factors(int val)
    {
        if (val == 1)
        {
            return;
        }
        for (int i = 2; i <= sqrt(val); ++i)
        {
            if (val % i == 0)
            {
                mt[val].push_back(i);
                all.insert(i);
                if (i != val / i)
                {
                    mt[val].push_back(val / i);
                    all.insert(val / i);
                }
            }
        }
        mt[val].push_back(val);
        all.insert(val);
    }

    int largestComponentSize(vector<int> &nums)
    {
        // i think finding the prime factors of each element and then grouping them on the basis of prime factors will help.
        for (auto it : nums)
        {
            find_factors(it);
        }
        int n = all.size();
        vector<int> halwa(all.begin(), all.end());
        UnionBySize *satwik = new UnionBySize(n);
        for (auto it : nums)
        {
            int temp = mt[it].size();
            vector<int> ind;
            for (auto val : mt[it])
            {
                ind.push_back(lower_bound(halwa.begin(), halwa.end(), val) - halwa.begin());
            }
            for (int i = 0; i < temp - 1; ++i)
            {
                satwik->unionsets(ind[i], ind[i + 1]);
            }
            if (!mt[it].empty())
            {
                satwik->size[satwik->find(ind[0])] += 1;
            }
        }
        return max(satwik->find_max_set(), 1);
    }
};
174116