<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 Solution1 {
    class DSU{
        vector<int> parent;
        vector<int> size;
    public:
        DSU(int n)
        {
            parent.assign(n, 0);
            size.assign(n, 0);
            for(int i = 0; i < n; i++)
            {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        int find(int x)
        {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }
        
        void Union(int x, int y)
        {
            int rootX = find(x);
            int rootY = find(y);
            
            if (rootX == rootY) 
                return;
            
            if (size[rootX] < size[rootY])
            {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            }
            else
            {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    };
public:
    int largestComponentSize(vector<int>& A) {
        int n = A.size();
        if (n <= 0) return 0;
        
        int maxVal = 0;
        // find the largest element in the input array A
        for(int x : A)
            if (x > maxVal) maxVal = x;
        
        DSU* dsu = new DSU(maxVal+1);
        
        // Get the factors of each input element and connect them
        for(int i = 0; i < n; i++)
        {
            int cur = A[i];
            for(int d = 2; d * d <= cur; d++)
            {
                if (cur%d == 0)
                {
                    dsu->Union(cur, d);
                    dsu->Union(cur, cur/d);
                }
            }
        }
        
        // find the largest connected component
        unordered_map<int, int> count;
        int ans = 0;
        for(auto element : A)
        {
            int cur_root = dsu->find(element);
            count[cur_root] += 1;
            ans = max(ans, count[cur_root]);
        }
        return ans;
    }
};

class Solution {
    class DSU{
        vector<int> parent;
        vector<int> size;
        int N;
    public:
        DSU(int n)
        {
            N = n;
            parent.assign(n, 0);
            size.assign(n, 0);
            for(int i = 0; i < n; i++)
            {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        int find(int x)
        {
            if (parent[x] != x)
                parent[x] = find(parent[x]);
            return parent[x];
        }
        
        void Union(int x, int y)
        {
            int rootX = find(x);
            int rootY = find(y);
            
            if (rootX == rootY) 
                return;
            
            if (size[rootX] < size[rootY])
            {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            }
            else
            {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
        }
    };
    
    vector<int> GetFactors(int x)
    {
        vector<int> res;
        for(int i = 2; i * i <= x; i++)
        {
            if ((x % i) == 0)
            {
                while(x % i == 0) x/= i;
                res.push_back(i);
            }
        }
        if (x > 1 || res.empty())
            res.push_back(x);
        
        return res;
    }
public:
    int largestComponentSize(vector<int>& A) {
        int n = A.size();
        if (n <= 0) return 0;
        
        vector<vector<int>> factored;
        for(int i = 0; i < n; i++)
        {
            factored.push_back(GetFactors(A[i]));
        }
        // [4,6,15,35]
        // (2), (2,3), (3,5), (5,7)
        
        
        set<int> primeNums; // 2,3,5,7
        for(auto factors : factored)
        {
            for(auto factor : factors)
                primeNums.insert(factor);
        }
        
        unordered_map<int, int> indexedPrimes;
        int idx = 0;
        // (0)2,(1)3,(2)5,(3)7
        for(auto itr = primeNums.begin(); itr != primeNums.end(); itr++)
            indexedPrimes[*itr] = idx++;
        
        DSU* dsu = new DSU(idx);
        for(auto factors : factored)
            for(auto factor : factors)
                dsu->Union(indexedPrimes[factors[0]], indexedPrimes[factor]);
        //(0,0), (0,0), (0,1), (1,1) (1,2), (2,2) (2,3)
        //0-0,1
        //1-1,2
        //2-2,3
        
        vector<int> count(idx, 0);
        for(auto factors : factored)
            count[dsu->find(indexedPrimes[factors[0]])]++;
        
        int ans = 0;
        for(int x : count)
            if (x > ans)
                ans = x;
        
        return ans;
    }
};
119196