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

解题思路

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

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

2. 传递性：如果 `a` 和 `b` 连通，`b` 和 `c` 连通，则 `a` 和 `c` 也连通。因此可以用并查集维护连通性。

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

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

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

Java 代码

```java
import java.util.*;

class Solution {
    public int countComponents(int[] nums, int threshold) {
        DSU dsu = new DSU(threshold);
        
        // 对于每个 num，将其与所有倍数用并查集合并
        for (int num : nums) {
            if (num > threshold) continue; // 大于 threshold 的数不参与并查集
            for (int j = num; j <= threshold; j += num) {
                dsu.unionSet(num, j);
            }
        }
        
        // 统计连通块数量
        Set<Integer> uniqueParents = new HashSet<>();
        for (int num : nums) {
            if (num > threshold) {
                // 大于 threshold 的数各自独立成一个连通块
                uniqueParents.add(num);
            } else {
                uniqueParents.add(dsu.find(num));
            }
        }
        
        return uniqueParents.size();
    }
}

/**
 * 并查集 (Disjoint Set Union)
 */
class DSU {
    private int[] parent;
    private int[] rank;
    
    public DSU(int n) {
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    
    public void unionSet(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            // 按秩合并
            if (rank[u] < rank[v]) {
                int temp = u;
                u = v;
                v = temp;
            }
            parent[v] = u;
            if (rank[u] == rank[v]) {
                rank[u]++;
            }
        }
    }
}
```

复杂度分析

- 时间复杂度：O(n × threshold/num 的平均值)，由于调和级数性质，总体约为 O(threshold × log(threshold))。并查集操作近似 O(α(n))。
- 空间复杂度：O(threshold)，用于并查集数组。

示例验证

- 示例1：`nums = [2,4,8,3,9], threshold = 5`
  - 大于 5 的数：8, 9 → 各自独立（2个连通块）
  - 小于等于 5 的数：2, 4, 3
  - 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个连通块
  - 小于等于 10 的数：2, 4, 8, 3, 9
  - 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.java](sandbox:///mnt/agents/output/leetcode_3378.java)