以下是 LeetCode 3378. 统计最小公倍数图中的连通块数目 的 Python3 实现：

解题思路

本题核心思路是 并查集 + 倍数枚举：

1. 关键观察：如果 `a` 能整除 `b`（即 `b` 是 `a` 的倍数）且 `b <= threshold`，则 `lcm(a, b) = b <= threshold`，所以 `a` 和 `b` 之间必有边。

2. 大于 threshold 的数：`lcm(a, b) >= max(a, b)`，所以若 `nums[i] > threshold`，它与任何数的 lcm 都大于 threshold，是孤立节点。

3. 枚举策略：对于每个 `num <= threshold`，枚举其所有倍数 `j = num, 2*num, 3*num, ... <= threshold`，将这些数与 `num` 用并查集合并。这样所有有公共因子的数最终会被合并到同一个连通块。

4. 统计答案：大于 threshold 的数各自独立；小于等于 threshold 的数通过并查集找根节点，统计不同根的数量。

Python3 代码

```python
from typing import List

class DSU:
    """并查集 (Disjoint Set Union)"""
    def __init__(self, n: int):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)
    
    def find(self, x: int) -> int:
        """查找根节点，带路径压缩"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, u: int, v: int) -> None:
        """合并两个集合，按秩合并"""
        u_root = self.find(u)
        v_root = self.find(v)
        if u_root == v_root:
            return
        # 按秩合并：将秩较小的树合并到秩较大的树下
        if self.rank[u_root] < self.rank[v_root]:
            u_root, v_root = v_root, u_root
        self.parent[v_root] = u_root
        if self.rank[u_root] == self.rank[v_root]:
            self.rank[u_root] += 1

class Solution:
    def countComponents(self, nums: List[int], threshold: int) -> int:
        dsu = DSU(threshold)
        
        # 对于每个 num <= threshold，将其与所有倍数用并查集合并
        for num in nums:
            if num > threshold:
                continue  # 大于 threshold 的数不参与并查集
            # 枚举 num 的所有倍数：num, 2*num, 3*num, ... <= threshold
            for j in range(num, threshold + 1, num):
                dsu.union(num, j)
        
        # 统计连通块数量
        unique_parents = set()
        for num in nums:
            if num > threshold:
                # 大于 threshold 的数各自独立成一个连通块
                unique_parents.add(num)
            else:
                unique_parents.add(dsu.find(num))
        
        return len(unique_parents)
```

复杂度分析

- 时间复杂度：O(threshold × log(threshold))。对于每个数 `num`，枚举其倍数的时间为 `threshold/num`，总和约为 `threshold × (1 + 1/2 + 1/3 + ...)` ≈ `threshold × log(threshold)`。并查集操作近似 O(α(n))。
- 空间复杂度：O(threshold)，用于并查集数组。

示例验证

- 示例1：`nums = [2,4,8,3,9], threshold = 5`
  - 大于 5 的数：8, 9 → 各自独立（2个连通块）
  - 2 的倍数：2, 4 → 合并 2 和 4
  - 3 的倍数：3（无其他倍数 ≤5）
  - 最终连通块：{2,4}, {3}, {8}, {9} → 4个

- 示例2：`nums = [2,4,8,3,9,12], threshold = 10`
  - 大于 10 的数：12 → 1个连通块
  - 2 的倍数：2, 4, 6, 8, 10 → 合并 2,4,8
  - 3 的倍数：3, 6, 9 → 合并 3,9
  - 通过 6（2×3），2的连通块和3的连通块连通
  - 最终连通块：{2,3,4,8,9}, {12} → 2个

下载文件：[leetcode_3378.py](sandbox:///mnt/agents/output/leetcode_3378.py)