麻了！领导私下跟我挺好的，一般中午也一起吃饭，但是他给我打的绩效是C，这是为什么？

带阈值的图连通性这个问题，说白了就是考察“阈值”这个门槛对图的连通性的影响。很多人在刷这类算法题的时候，容易被题目的描述绕进去，最后整出个时间复杂度爆炸的解法，自己还不知道哪里出了问题 🤦‍♂️。

咱们直接点，说白了，这类问题一般可以拆解成：并查集 + 离线查询，关键在于理解如何高效地构建连通分量，并在查询时快速确定两个点是否连通。Java 选手们看到这两个词，应该已经想到 Union-Find 这个老朋友了吧？

class UnionFind {
    int[] parent, rank;
        public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

好了，UnionFind 写好了，接下来该考虑“带阈值”这个点了。题目一般会给出一个权重阈值 threshold，意思是如果一条边的权重小于 threshold，那就当它不存在。这其实很好处理，我们只需要先把所有权重大于等于 threshold 的边按权重排序，然后依次合并它们。

离线处理查询

查询一般是给定 query(a, b)，问这两个点是否连通。这里聪明的同学可能已经发现了，我们可以先把边按权重降序排序，然后依次处理查询，把合适的边加入 UnionFind 后再检查连通性。

public boolean[] areConnected(int n, int threshold, int[][] queries) {
    UnionFind uf = new UnionFind(n + 1); // n+1 是因为节点从 1 开始
    for (int i = threshold + 1; i <= n; i++) { 
        for (int j = 2 * i; j <= n; j += i) {
            uf.union(i, j); // 只合并符合条件的边
        }
    }
    boolean[] res = new boolean[queries.length];
    for (int i = 0; i < queries.length; i++) {
        res[i] = uf.find(queries[i][0]) == uf.find(queries[i][1]);
    }
    return res;
}

复杂度分析

1. 并查集操作（路径压缩+按秩合并）：均摊 O(α(n))，几乎是 O(1)。
2. 构建连通分量：O(n log n)，因为遍历了所有 i，并合并倍数 j。
3. 查询：每次 O(1)，总共 O(q)。

所以，总体时间复杂度大概是 O(n log n + q)，这在大部分情况下都能接受。

可能的坑

• threshold 太大，导致所有点都孤立，那直接返回 false 数组就完事了 😆。
• threshold == 0 时，所有点都是连通的，直接返回 true 数组。
• 题目中 n 和 queries 规模可能很大，所以要注意 O(n^2) 的暴力解法是不可接受的。

总之，这道题的精髓在于：

1. 用 并查集 管理连通分量。
2. 按需合并 符合条件的边，而不是一开始就加进去。
3. 离线查询，避免每次查询都重新遍历整个图。

刷题的朋友们记住这个套路，下次再遇到类似问题，直接 Union-Find 套上去，打完收工 😎！