难度: Hard
给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：
nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。返回 图中最大连通组件的大小 。
示例 1：
输入：nums = [4,6,15,35] 输出：4
示例 2：
输入：nums = [20,50,9,63] 输出：2
示例 3：
输入：nums = [2,3,6,7,4,12,21,39] 输出：8
提示：
1 <= nums.length <= 2 * 1041 <= nums[i] <= 105nums 中所有值都 不同运行时间: 304 ms
内存: 30.3 MB
N = 10 ** 5 + 1
primes = []
is_prime = [True] * N
decompose = [[] for _ in range(N)]
for i in range(2, N):
if not is_prime[i]:
continue
primes.append(i)
decompose[i].append(i)
for j in range(i*2, N, i):
is_prime[j] = False
decompose[j].append(i)
d = {p: i for i, p in enumerate(primes, 1)}
# 处理num == 1的特殊情况
d[1] = 0
decompose[1].append(1)
class UnionSet:
__slots__ = ("arr", "rank")
def __init__(self, n):
self.arr = list(range(n))
self.rank = [0] * n
def find(self, a):
_arr = self.arr
if _arr[a] != a:
_arr[a] = self.find(_arr[a])
return _arr[a]
def link(self, a, b):
if (pa := self.find(a)) == (pb := self.find(b)):
return
_rank = self.rank
if _rank[pa] < _rank[pb]:
self.arr[pa] = pb
elif _rank[pa] > _rank[pb]:
self.arr[pb] = pa
else:
self.arr[pa] = pb
_rank[pb] += 1
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
# +1是为num==1预留空间
us = UnionSet(bisect_right(primes, max(nums)) + 1)
for facs in map(decompose.__getitem__, nums):
for a, b in pairwise(facs):
us.link(d[a], d[b])
return max(
Counter(
us.find(d[facs[0]])
for facs in map(decompose.__getitem__, nums)
).values()
)
题解采用了素数筛法结合并查集的方法来解决问题。首先，使用埃拉托斯特尼筛法预先计算出所有小于等于100000的素数，并为每个数标记它的素数因子。然后，对于每个输入数字，通过它的素数因子来定义它在图中的节点。如果两个数有共同的素数因子，它们在图中就是相连的。这样，问题转化为了找出具有共同素数因子的最大连通组件。使用并查集来处理节点的连接和组件的合并。最后，遍历输入数组，对每个数的素数因子进行并查集合并操作，最终通过计数并查集根的频率来确定最大的连通组件大小。
时间复杂度: O(n log log n + m log n)
空间复杂度: O(n + m)
N = 10 ** 5 + 1
primes = []
is_prime = [True] * N
decompose = [[] for _ in range(N)]
for i in range(2, N):
if not is_prime[i]:
continue
primes.append(i)
decompose[i].append(i)
for j in range(i*2, N, i):
is_prime[j] = False
decompose[j].append(i)
d = {p: i for i, p in enumerate(primes, 1)}
d[1] = 0
decompose[1].append(1)
class UnionSet:
__slots__ = ("arr", "rank")
def __init__(self, n):
self.arr = list(range(n))
self.rank = [0] * n
def find(self, a):
_arr = self.arr
if _arr[a] != a:
_arr[a] = self.find(_arr[a])
return _arr[a]
def link(self, a, b):
if (pa := self.find(a)) == (pb := self.find(b)):
return
_rank = self.rank
if _rank[pa] < _rank[pb]:
self.arr[pa] = pb
elif _rank[pa] > _rank[pb]:
self.arr[pb] = pa
else:
self.arr[pa] = pb
_rank[pb] += 1
class Solution:
def largestComponentSize(self, nums: List[int]) -> int:
us = UnionSet(bisect_right(primes, max(nums)) + 1)
for facs in map(decompose.__getitem__, nums):
for a, b in pairwise(facs):
us.link(d[a], d[b])
return max(
Counter(
us.find(d[facs[0]])
for facs in map(decompose.__getitem__, nums)
).values()
)
埃拉托斯特尼筛法（Sieve of Eratosthenes）是一种高效且简单的方法来找出小于或等于给定数的所有素数。该方法的时间复杂度为O(n log log n)，比其他简单方法更快，特别是当需要处理大量数据时。此外，它的空间效率也很高，只需要一个布尔数组来标记非素数。这些特点使得埃拉托斯特尼筛法在处理需要预先计算大量素数的问题时非常合适，这也是为什么在这个题解中选择使用它来预处理素数。
并查集是一种数据结构，它可以高效地处理一些不交集的合并及查询问题。在本题中，使用并查集来管理节点（数的素数因子）的连接状态，从而快速确定哪些数是通过共享素数因子相互连接的。算法中，每次两个数的素数因子发现有共同项时，就通过并查集的`link`操作将它们所属的集合合并。最后，通过遍历所有数的素数因子，并查集中的根节点的频率，可以找到最大的连通组件的大小。这种方法能够有效地将问题从直接处理数转变为处理数的素数分解，大大简化了问题的复杂度。
在并查集中，`rank`通常用来表示每个节点的树的深度（或近似深度）。比较`rank`并根据它选择合并策略的方法被称为按秩合并。该策略的目的是尽可能保持树的深度小，从而优化并查集的操作效率。具体来说，如果两个节点的树的`rank`不同，我们将深度较小的树连接到深度较大的树上；如果它们的深度相同，则选择其中一个作为根，并将其`rank`增加1。这种方法可以减少路径长度，进一步优化查找的时间复杂度，使并查集的操作更加高效。