952. Largest Component Size by Common Factor.md

952. Largest Component Size by Common Factor

Question:

Given a non-empty array of unique positive integers A, consider the following graph:

• There are A.length nodes, labelled A[0] to A[A.length - 1];
• There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

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

Example 1:

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

Example 2:

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

Example 3:

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

Note:

• 1 <= A.length <= 20000
• 1 <= A[i] <= 100000

Solution:

• Method 1: Union find set

  class Solution {
      private int[] uf;
      public int largestComponentSize(int[] A) {
          if(A == null || A.length == 0) return 0;
          int max = A[0];
          for(int i = 1; i < A.length; i++) max = Math.max(max, A[i]);
          this.uf = new int[max + 1];
          for(int i = 0; i < uf.length; i++) this.uf[i] = i;
          // For every number, find their factor and add to uf.
          for(int i = 0; i < A.length; i++){
              for(int j = 2; j <= (int)Math.sqrt(A[i]); j++){
                  if(A[i] % j == 0){
                      union(A[i], j);
                      union(A[i], A[i] / j);
                  }
              }
          }
          Map<Integer, Integer> map = new HashMap<>();
          int res = 1;
          for(int i = 0; i < A.length; i++){
              int root = find(A[i]);
              int cur = map.containsKey(root) ? map.get(root): 0;
              map.put(root, ++cur);
              res = Math.max(res, cur);
          }
          return res;
      }
      private void union(int i, int j){
          int p = find(i);
          int q = find(j);
          uf[p] = q;
      }
      private int find(int j){
          if(uf[j] != j){
              uf[j] = find(uf[j]);
          }
          return uf[j];
      }
  }

Reference

1. 花花酱 LeetCode 952. Largest Component Size by Common Factor