mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
51 lines
2.2 KiB
HTML
51 lines
2.2 KiB
HTML
<p>You are given an array of integers <code>nums</code> of size <code>n</code> and a <strong>positive</strong> integer <code>threshold</code>.</p>
|
|
|
|
<p>There is a graph consisting of <code>n</code> nodes with the <code>i<sup>th</sup></code> node having a value of <code>nums[i]</code>. Two nodes <code>i</code> and <code>j</code> in the graph are connected via an <strong>undirected</strong> edge if <code>lcm(nums[i], nums[j]) <= threshold</code>.</p>
|
|
|
|
<p>Return the number of <strong>connected components</strong> in this graph.</p>
|
|
|
|
<p>A <strong>connected component</strong> is a subgraph of a graph in which there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.</p>
|
|
|
|
<p>The term <code>lcm(a, b)</code> denotes the <strong>least common multiple</strong> of <code>a</code> and <code>b</code>.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [2,4,8,3,9], threshold = 5</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">4</span></p>
|
|
|
|
<p><strong>Explanation:</strong> </p>
|
|
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2024/10/31/example0.png" style="width: 250px; height: 251px;" /></p>
|
|
|
|
<p> </p>
|
|
|
|
<p>The four connected components are <code>(2, 4)</code>, <code>(3)</code>, <code>(8)</code>, <code>(9)</code>.</p>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<div class="example-block">
|
|
<p><strong>Input:</strong> <span class="example-io">nums = [2,4,8,3,9,12], threshold = 10</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io">2</span></p>
|
|
|
|
<p><strong>Explanation:</strong> </p>
|
|
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2024/10/31/example1.png" style="width: 250px; height: 252px;" /></p>
|
|
|
|
<p>The two connected components are <code>(2, 3, 4, 8, 9)</code>, and <code>(12)</code>.</p>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= nums.length <= 10<sup>5</sup></code></li>
|
|
<li><code>1 <= nums[i] <= 10<sup>9</sup></code></li>
|
|
<li>All elements of <code>nums</code> are unique.</li>
|
|
<li><code>1 <= threshold <= 2 * 10<sup>5</sup></code></li>
|
|
</ul>
|