#3378

Count Connected Components in LCM Graph

international master · 1955 · lc hard +32 · 31.1% accepted · 83 likes · top 9%

Description

You are given an array of integers nums of size n and a positive integer threshold.

Construct a graph of n nodes where the i^th node has value nums[i]. Connect nodes i and j with an undirected edge when lcm(nums[i], nums[j]) <= threshold.

Return the number of connected components in this graph.

A connected component is a maximal set of vertices with a path between every pair, sharing no edge with any vertex outside the set.

lcm(a, b) denotes the least common multiple of a and b.

Code

1

2

3

class Solution:
    def countComponents(self, nums: List[int], threshold: int) -> int:

class Solution:
    def countComponents(self, nums: List[int], threshold: int) -> int: