0952. Largest Component Size by Common Factor

题目信息

题号:

0952

难度:

Hard

主题:

数组、公共因子、连通分量

原题:

LeetCode 0952

重点:

每个数组元素实例视为一个图节点;两个数只要存在大于 1 的公共因子就直接相连,答案按传递连通后的节点数量计算

题目重述

给定由互不相同正整数组成的数组 nums。把每个数组元素视为图中的一个节点。若两个元素的最大公约数大于 1,即它们共享某个大于 1 的因子,则在对应节点之间连接一条无向边。

直接没有公共因子的两个数仍可能通过其他数间接连通。请返回该图中节点数最多的连通分量大小。

1 <= nums.length <= 2 * 10^4,1 <= nums[i] <= 10^5,数组元素互不相同。

自建示例

三个数通过不同因子连成一组:

输入:nums = [6,10,15,7]
输出:3
解释:6 与 10 共享因子 2,6 与 15 共享因子 3,10 与 15 共享因子 5,因此前三个节点连通;7 单独成组。

数组只有一个数:

输入:nums = [13]
输出:1
解释:图中只有一个节点,它自身构成大小为 1 的唯一连通分量。