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``,数组元素互不相同。 自建示例 -------- 三个数通过不同因子连成一组: .. code-block:: text 输入:nums = [6,10,15,7] 输出:3 解释:6 与 10 共享因子 2,6 与 15 共享因子 3,10 与 15 共享因子 5,因此前三个节点连通;7 单独成组。 数组只有一个数: .. code-block:: text 输入:nums = [13] 输出:1 解释:图中只有一个节点,它自身构成大小为 1 的唯一连通分量。