3378. Count Connected Components in LCM Graph Hard

1/**
2 * [3378] Count Connected Components in LCM Graph
3 *
4 * You are given an array of integers nums of size n and a positive integer threshold.
5 * There is a graph consisting of n nodes with the i^th node having a value of nums[i]. Two nodes i and j in the graph are connected via an undirected edge if lcm(nums[i], nums[j]) <= threshold.
6 * Return the number of connected components in this graph.
7 * A connected component 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.
8 * The term lcm(a, b) denotes the least common multiple of a and b.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">nums = [2,4,8,3,9], threshold = 5</span>
13 * Output: <span class="example-io">4</span>
14 * Explanation: 
15 * <img alt="" src="https://assets.leetcode.com/uploads/2024/10/31/example0.png" style="width: 250px; height: 251px;" />
16 *  
17 * The four connected components are (2, 4), (3), (8), (9).
18 * </div>
19 * <strong class="example">Example 2:
20 * <div class="example-block">
21 * Input: <span class="example-io">nums = [2,4,8,3,9,12], threshold = 10</span>
22 * Output: <span class="example-io">2</span>
23 * Explanation: 
24 * <img alt="" src="https://assets.leetcode.com/uploads/2024/10/31/example1.png" style="width: 250px; height: 252px;" />
25 * The two connected components are (2, 3, 4, 8, 9), and (12).
26 * </div>
27 *  
28 * Constraints:
29 * 
30 * 	1 <= nums.length <= 10^5
31 * 	1 <= nums[i] <= 10^9
32 * 	All elements of nums are unique.
33 * 	1 <= threshold <= 2 * 10^5
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/count-connected-components-in-lcm-graph/
39// discuss: https://leetcode.com/problems/count-connected-components-in-lcm-graph/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn count_components(nums: Vec<i32>, threshold: i32) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_3378() {
57    }
58}
59