首页算法

1627. 带阈值的图连通性

难度困难

有 n 座城市，编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是： x 和 y 的公因数中，至少有一个 严格大于 某个阈值 threshold 。更正式地说，如果存在整数 z ，且满足以下所有条件，则编号 x 和 y 的城市之间有一条道路：

  • x % z == 0
  • y % z == 0
  • z > threshold

给你两个整数 n 和 threshold ，以及一个待查询数组，请你判断每个查询 queries[i] = [ai, bi] 指向的城市 ai 和 bi 是否连通（即，它们之间是否存在一条路径）。

返回数组 answer ，其中 answer.length == queries.length 。如果第 i 个查询中指向的城市 ai 和 bi 连通，则 answer[i] 为 true ；如果不连通，则 answer[i] 为 false 。

示例 1：

img

输入：n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]

输出：[false,false,true]

解释：每个数的因数如下：
1: 1
2: 1, 2
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
所有大于阈值的的因数已经加粗标识，只有城市 3 和 6 共享公约数 3 ，因此结果是：
[1,4] 1 与 4 不连通
[2,5] 2 与 5 不连通
[3,6] 3 与 6 连通，存在路径 3--6

示例 2：

img

输入：n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]

输出：[true,true,true,true,true]

解释：每个数的因数与上一个例子相同。但是，由于阈值为 0 ，所有的因数都大于阈值。因为所有的数字共享公因数 1 ，所以所有的城市都互相连通。

示例 3：

img

输入：n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]

输出：[false,false,false,false,false]

解释：只有城市 2 和 4 共享的公约数 2 严格大于阈值 1 ，所以只有这两座城市是连通的。

注意，同一对节点 [x, y] 可以有多个查询，并且查询 [x，y] 等同于查询 [y，x] 。

提示：

  • 2 <= n <= 10^4
  • 0 <= threshold <= n
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 1 <= ai, bi <= cities
  • ai != bi

# 分解因数 + 并查集

class Solution {
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
        // 分解因数 + 并查集
        // 以因数作为转折点
        init(n + 1);
        // 枚举公因数
        for (int z = threshold + 1; z <= n; z++) {
            int num = z;
            // 枚举两个 z 的倍数的点并连接
            //  两两连接
            for (int i = z, j = 2 * z; j <= n; i += z, j += z) {
                union(i, j);
            }
            /*
            // 直接枚举是 z 的倍数的点
            for (int i = 1; i * z <= n; i++) {
                union (z, i * z);
            }
            */
        }
        // 检查连通分量
        List<Boolean> ans = new ArrayList<>();
        for (int[] query : queries) {
            ans.add(find(query[0]) == find(query[1]));
        }
        return ans;
    }
    int[] father;
    public void init(int n) {
        father = new int[n];
        for (int i = 1; i < n; i++) {
            father[i] = i;
        }
    }
    public void union(int i, int j) {
        int lAncestor = find(i);
        int rAncestor = find(j);
        // 让质因数的父节点指向原数
        // 这样在分组的时候使得父节点不会超过 n
        // - cnt[find(i)]++;
        father[rAncestor] = lAncestor;
    }
    public int find(int x) {
        if (x == father[x]) {
            return x;
        }
        return father[x] = find(father[x]);
    }
}
# 埃式筛 + 并查集




埃拉托斯特尼筛法：


    

  1. 

    列出 2 以后的所有序列：
    

    2. 

  2. 

      

    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
      • 

    

    3. 

  3. 

    标出序列中的第一个素数，也就是 2，序列变成：
    

    4. 

  4. 

      

    • 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
      • 

    

    5. 

  5. 

    将剩下序列中，划掉 2 的倍数，序列变成：
    

    6. 

  6. 

      

    • 2 3 5 7 9 11 13 15 17 19 21 23 25
      • 

    

    7. 

  7. 

    如果这个序列中最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数，否则回到第二步。
    

    8. 

  8. 

    本例中，因为 25 大于 2 的平方，我们返回第二步：
    

    9. 

  9. 

    剩下的序列中第一个素数是 3，将主序列中 3 的倍数划掉，主序列变成：
    

    10. 

  10. 

      

    • 2 3 5 7 11 13 17 19 23 25
      • 

    

    11. 

  11. 

    我们得到的素数有：2，3
    

    12. 

  12. 

    25 仍然大于 3 的平方，所以我们还要返回第二步：
    

    13. 

  13. 

    序列中第一个素数是 5，同样将序列中 5 的倍数划掉，主序列成了：
    

    14. 

  14. 

      

    • 2 3 5 7 11 13 17 19 23
      • 

    

    15. 

  15. 

    我们得到的素数有：2，3，5 。
    

    16. 

  16. 

    因为 23 小于 5 的平方，跳出循环.
    

    17. 



结论：2 到 25 之间的素数是：2 3 5 7 11 13 17 19 23。




// 枚举公因数
for (int z = threshold + 1; z <= n; z++) {
    if (used[z]) {
        continue;
    }
    int num = z;
    // 枚举两个 z 的倍数的点并连接
    //  两两连接
    for (int i = z, j = 2 * z; j <= n; i += z, j += z) {
        // 剔除 j
        used[j] = true;
        union(i, j);
    }
}


并查集 + 数学