题目

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:

  1. Input: [4,6,15,35]
  2. Output: 4

image.png

Example 2:

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

image.png

Example 3:

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

image.png

Note:

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

题意

给定一串正整数，将其中具有相同因数(>=2)的整数两两相连，求这样操作后最大连通分量中结点的数量。

思路

并查集处理。对于每一个整数，找到它所有大于2的因数，将该因数和整数本身添加到一个组中。最后统计每个组中数组中整数出现的次数即可。

代码实现

Java

  1. class Solution {
  2.     public int largestComponentSize(int[] A) {
  3.         int maxSize = 0, maxNum = 0;
  4.         // 找到最大整数
  5.         for (int num : A) {
  6.             maxNum = Math.max(maxNum, num);
  7.         }
  9.         Map<Integer, Integer> map = new HashMap<>();
  10.         int[] root = new int[maxNum + 1];
  11.         for (int i = 1; i <= maxNum; i++) {
  12.             root[i] = i;
  13.         }
  15.         for (int num : A) {
  16.             for (int i = 2; i <= (int) Math.sqrt(num); i++) {
  17.                 if (num % i == 0) {
  18.                     int j = num / i;
  19.                     union(root, num, i);
  20.                     union(root, num, j);
  21.                 }
  22.             }
  23.         }
  25.         for (int num : A) {
  26.             int tmp = findRoot(root, num);
  27.             int size = map.getOrDefault(tmp, 0) + 1;
  28.             map.put(tmp, size);
  29.             maxSize = Math.max(maxSize, size);
  30.         }
  32.         return maxSize;
  33.     }
  35.     private void union(int[] root, int x, int y) {
  36.         int rootX = findRoot(root, x), rootY = findRoot(root, y);
  37.         if (rootX != rootY) {
  38.             root[rootX] = rootY;
  39.         }
  40.     }
  42.     private int findRoot(int[] root, int x) {
  43.         // 路径压缩
  44.         return root[x] == x ? x : (root[x] = findRoot(root, root[x]));
  45.     }
  46. }