You are given an integer array of unique positive integers nums. Consider the following graph:


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


Return the size of the largest connected component in the graph.

&nbsp;
Example 1:

Input: nums = [4,6,15,35]
Output: 4


Example 2:

Input: nums = [20,50,9,63]
Output: 2


Example 3:

Input: nums = [2,3,6,7,4,12,21,39]
Output: 8


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 2 * 104
	1 &lt;= nums[i] &lt;= 105
	All the values of nums are unique.


class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        
        def find(node):
            if parent[node] == -1: return node
            else:
                parent[node] = find(parent[node])
                return parent[node]
        
        def union(idx1,idx2):
            par1,par2 = find(idx1),find(idx2)
            if par1!=par2:
                if rank[par1] > rank[par2]:
                    parent[par2] = par1
                elif rank[par2] > rank[par1]:
                    parent[par1] = par2
                else:
                    parent[par2] = par1
                    rank[par1] += 1
        
        n = len(nums)
        parent = defaultdict(lambda:-1)
        rank = defaultdict(lambda:0)
        for i in range(n):
            limit = int(nums[i]**0.5)
            for j in range(2,limit+1):
                if nums[i] % j == 0:
                    union(nums[i],j)
                    union(nums[i],nums[i]//j)
        count = defaultdict(lambda:0)
        best = -1
        for num in nums:
            par = find(num)
            tmp = count[par] + 1
            if tmp > best: best = tmp
            count[par] = tmp
        return best
class Solution {
    public int largestComponentSize(int[] nums) {
        int maxNum = getMaxNum(nums);
        Map<Integer, Integer> numToFirstPrimeFactor = new HashMap<>();
        DisjointSet ds = new DisjointSet(maxNum + 1);
        for (int num : nums) {
            if (num == 1) {
                continue;
            }

            List<Integer> primeFactors = getPrimeFactors(num);
            int firstPrimeFactor = primeFactors.get(0);
            numToFirstPrimeFactor.put(num, firstPrimeFactor);

            for (int i = 1; i < primeFactors.size(); i++) {
                ds.union(primeFactors.get(i-1), primeFactors.get(i));
            }
        }

        Map<Integer, Integer> componentToSize = new HashMap<>();
        int maxSize = 0;
        for (int num : nums) {
            if (num == 1) {
                continue;
            }

            int firstPrimeFactor = numToFirstPrimeFactor.get(num);
            int component = ds.find(firstPrimeFactor);
            int size = componentToSize.getOrDefault(component, 0);
            componentToSize.put(component, ++size);
            maxSize = Math.max(maxSize, size);
        }
        return maxSize;
    }

    public int getMaxNum(int[] nums) {
        int maxNum = 0;
        for (int num : nums) {
            maxNum = Math.max(maxNum, num);
        }
        return maxNum;
    }

    public List<Integer> getPrimeFactors(int num) {
        List<Integer> primeFactors = new ArrayList<>();

        // even prime factor i.e. 2
        if((num & 1) == 0){
            primeFactors.add(2);

            do{
                num >>= 1;
            }while((num & 1) == 0);
        }

        // odd prime factors
        int primeFactor = 3;
        while(num != 1 && primeFactor*primeFactor <= num){
            if(num % primeFactor == 0){
                primeFactors.add(primeFactor);

                do{
                    num /= primeFactor;
                }while(num % primeFactor == 0);
            }
            primeFactor += 2;
        }

        // num is prime
        if(num != 1){
            primeFactors.add(num);
        }
        return primeFactors;
    }
}

class DisjointSet {
    int[] root;
    int[] rank;

    public DisjointSet(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        while (x != root[x]) {
            root[x] = root[root[x]];
            x = root[x];
        }
        return x;
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return;
        }

        if (rank[rootX] > rank[rootY]) {
            root[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            root[rootX] = rootY;
        } else {
            root[rootY] = rootX;
            rank[rootX]++;
        }
    }
}
class Solution {
private:
    vector<bool> sieve(int n) {
        vector<bool> prime(n + 1);
        for (int i = 0; i <= n; i++)
            prime[i] = 1;
        for (int p = 2; p * p <= n; p++) {
            if (prime[p] == 1) {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = 0;
            }
        }
        prime[1] = prime[0] = 0;
        return prime;
    }
    vector<int> factors(int n, vector<int> &primelist) {
        vector<int> facs;
        for (int i = 0; primelist[i] * primelist[i] <= n && i < primelist.size(); i++) {
            if (n % primelist[i] == 0) {
                facs.push_back(primelist[i]);
                while (n % primelist[i] == 0) {
                    n /= primelist[i];
                }
            }
        }
        if (n > 1) facs.push_back(n);
        return facs;
    }
    void dfs(vector<vector<int>> &gr, int node, vector<int> &vis, int &compSize) {
        if(vis[node]) return;
        vis[node] = 1;
        compSize++;
        for(auto x : gr[node]) {
            dfs(gr, x, vis, compSize);
        }
    }
public:
    int largestComponentSize(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> gr(n);
        vector<bool> prime = sieve(1e5 + 6);
        vector<int> primelist;
		// Getting all the primes till 10^5 as maximum value of nums[i] is 10^5
        for (int i = 2; i <= 1e5 + 5; i++) if (prime[i]) primelist.push_back(i);
        unordered_map<int, int> m; // to store the index of the node with prime factor x
        for(int i = 0; i < n; i++) {
            vector<int> facs = factors(nums[i], primelist);
            for(auto j : facs) {
                if(m.find(j) == m.end()) { // prime factor had not occured before
                    m[j] = i; // j is the prime factor and its index is i
                } else {
				    // prime factor has already been seen before in a previous number and nums[i] is connected to that number
                    gr[i].push_back(m[j]);
                    gr[m[j]].push_back(i);
                }
            }
        }
        int ans = 0;
        vector<int> vis(n);
        for(int i = 0; i < n; i++) { // running a simple dfs to calculate the maximum component size
            if(!vis[i]) {
                int compSize = 0;
                dfs(gr, i, vis, compSize);
                ans = max(ans, compSize);
            }
        }
        return ans;
    }
};
var largestComponentSize = function(nums) {
  const rootByFactor = new Map();
  const parents = new Array(nums.length);

  function addFactor(i, factor) {
    if (rootByFactor.has(factor)) {
      let r = rootByFactor.get(factor);
      while (parents[i] != i) i = parents[i];
      while (parents[r] != r) r = parents[r];
      parents[i] = r;
    }
    rootByFactor.set(factor, parents[i]);
  }

  for (const [i, num] of nums.entries()) {
    parents[i] = i;
    addFactor(i, num);
    for (let factor = 2; factor * factor <= num; ++factor) {
      if (num % factor == 0) {
        addFactor(i, factor);
        addFactor(i, num / factor);
      }
    }
  }

  let largest = 0;
  const sums = new Array(nums.length).fill(0);
  for (let r of parents) {
    while (parents[r] != r) r = parents[r];
    largest = Math.max(largest, ++sums[r]);
  }
  return largest;
};
Largest Component Size by Common Factor