0952. Largest Component Size by Common Factor¶
题目信息¶
- 题号:
0952
- 难度:
Hard
- 主题:
数组、公共因子、连通分量
- 原题:
- 重点:
每个数组元素实例视为一个图节点;两个数只要存在大于
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 的唯一连通分量。