<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 {
private :
    int cnt ;
    int mx_sz ;
    std :: vector<int> par ;
    std :: vector<int> size ;
public:
    DSU( int n ) : cnt( n ) , mx_sz( 1 ) , par( n + 1 ) , size( n + 1 ,1 )
    {
        iota( par.begin() , par.end() , 0 ) ;
    }
    void setSize( int a ){
        size[ a ] = 1 ;
    }

    int find( int a )
    {
        return  par[a] = par[a] == a ? a : find(par[a]) ;
    }

    int merge( int a , int b )
    {
        a = find( a ) ; b = find( b ) ;

        if ( a == b ) return 0 ;

        if ( size[a] < size[b] )swap(a, b) ;

        par[ b ] = a ;
        size[a] += size[b] ;

        mx_sz = std :: max( mx_sz , size[a] ) ;
        --cnt ;

        return 1 ;
    }

    bool connected(int u, int v)
    {
        return find(u) == find(v);
    }
    int groupSize( int u )
    {
        return size[ find(u) ] ;
    }
    int maxGroupSize(  )
    {
        return mx_sz ;
    }
    int totalSize()
    {
        return cnt ;
    }
    void reset(int u)
    {
        par[u] = u;
        // rank[u] = 0;
    }
    ~DSU(){
        for( int i = 0 ; i < min( 23 , (int)par.size() ) ; i++ )
        cout<< par[i] << ' ' ;
    }

};
class Solution {
public:
    int largestComponentSize(vector<int>& nums) {
        
        vector< int > isPresent ;
        int n = 0 ; 
        for( auto & a : nums )
        {
            if( isPresent.size() <= a) isPresent.resize( a + 1 );
            isPresent[ a ] = 1 ;
            n = max( n , a ) ;
        } 
        DSU d( n+1 ) ;
        // for( auto & a : nums ) d.setSize( a ) ;

        for( int i = 2 ; i  <= n ; i++ )
        {
            int curr = 0 ;
            for( int j = i   ; j <= n ; j += i  )
             {
                  if( isPresent[j] )
                  {
                    if( curr == 0 ) curr = j ;
                    else d.merge( curr , j ) ;
                  }
             }
        }
        return d.maxGroupSize() ;
    }
};
95168