952.按公因数计算最大组件大小.md

952.按公因数计算最大组件大小

/*
 * @lc app=leetcode.cn id=952 lang=typescript
 *
 * [952] 按公因数计算最大组件大小
 */

// @lc code=start
function largestComponentSize(a: number[]): number {}
// @lc code=end

解法 1: 并查集

function largestComponentSize(a: number[]): number {
  const N = Math.max(...a),
    n = a.length

  const p = [...new Array(n).keys()]
  const find = (i: number) => {
    while (i !== p[i]) {
      p[i] = p[p[i]]
      i = p[i]
    }
    return p[i]
  }
  const union = (i: number, j: number) => {
    const ri = find(i),
      rj = find(j)
    if (ri !== rj) p[rj] = ri
  }

  const primes = getPrimes(N)
  const b = new Map<number, number>()
  for (let [i, num] of a.entries()) {
    for (let k of primes) {
      if (k > num) break
      if (num % k === 0) {
        while (num % k === 0) num /= k
        if (b.has(k)) union(b.get(k)!, i)
        else b.set(k, i)
      }
      if (primes.has(num)) break
    }
    if (num > 1) {
      if (b.has(num)) union(b.get(num)!, i)
      else b.set(num, i)
    }
  }
  let cnt = new Map<number, number>()
  for (let i = 0; i < n; i++) {
    const root = find(i)
    cnt.set(root, (cnt.get(root) ?? 0) + 1)
  }
  let res = 0
  for (let [_, c] of cnt) {
    res = Math.max(res, c)
  }
  return res
}

function getPrimes(n: number) {
  const nums = new Array(n + 1).fill(1)
  nums[0] = nums[1] = 0
  const primes = new Set<number>()
  for (let i = 2; i <= n; i++) {
    if (nums[i]) primes.add(i)
    for (let num of primes) {
      const j = num * i
      if (j > n) break
      nums[j] = 0
      if (i % num === 0) break
    }
  }

  return primes
}

Case

test.each([
  { input: { nums: [4, 6, 15, 35] }, output: 4 },
  { input: { nums: [20, 50, 9, 63] }, output: 2 },
  { input: { nums: [2, 3, 6, 7, 4, 12, 21, 39] }, output: 8 },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(largestComponentSize(nums)).toEqual(output)
})