Hard

题目描述

我们有 n 个城市，标号为 1 到 n。当且仅当城市 x 和 y 有一个大于某个阈值的公共因子时，标号为 x 和 y 的两个不同城市之间才会有一条双向道路直接连接。

更正式地说，如果存在整数 z 满足以下所有条件，那么标号为 x 和 y 的城市之间就有一条道路：

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

给定两个整数 n 和 threshold，以及一个查询数组 queries，你必须判断每个查询 queries[i] = [ai, bi] 中城市 ai 和 bi 是否直接或间接连通（即它们之间存在某条路径）。

返回一个数组 answer，其中 answer.length == queries.length，如果第 i 个查询中 ai 和 bi 之间存在路径，则 answer[i] 为 true，否则为 false。

示例 1：

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

示例 2：

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

示例 3：

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

约束条件：

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

解题思路

这是一个图的连通性问题，可以使用并查集来解决。

核心思路：

  1. 建图过程：两个城市 x 和 y 连通当且仅当它们有大于 threshold 的公共因子。我们需要找到所有这样的城市对并用并查集连接它们。

  2. 优化建图：直接枚举所有城市对会超时。关键观察是：如果两个数有公共因子 d > threshold，那么它们都是 d 的倍数。因此我们可以：

    • 遍历所有可能的因子 d（从 threshold+1 到 n）
    • 对于每个因子 d，找到所有它的倍数：d, 2d, 3d, …
    • 将这些倍数连接在同一个连通分量中

  3. 并查集操作：

    • 对于因子 d 的所有倍数，我们将它们依次连接：连接 d 和 2d，连接 2d 和 3d，以此类推
    • 这样所有 d 的倍数就都在同一个连通分量中了

  4. 查询处理：对于每个查询 [a, b]，只需检查 a 和 b 是否在同一个连通分量中。

时间复杂度分析：

  • 建图：O(n log n)，因为对每个因子 d，需要处理 n/d 个倍数
  • 查询：O(α(n)) 每次查询，其中 α 是阿克曼函数的反函数

代码实现

class Solution {
public:
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
    
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        parent.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        // 对于每个大于threshold的因子，连接其所有倍数
        for (int d = threshold + 1; d <= n; d++) {
            vector<int> multiples;
            for (int multiple = d; multiple <= n; multiple += d) {
                multiples.push_back(multiple);
            }
            
            // 连接所有倍数
            for (int i = 1; i < multiples.size(); i++) {
                unite(multiples[0], multiples[i]);
            }
        }
        
        vector<bool> result;
        for (auto& query : queries) {
            result.push_back(find(query[0]) == find(query[1]));
        }
        
        return result;
    }
};

class Solution:
    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:
        parent = list(range(n + 1))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        # 对于每个大于threshold的因子，连接其所有倍数
        for d in range(threshold + 1, n + 1):
            multiples = list(range(d, n + 1, d))
            
            # 连接所有倍数
            for i in range(1, len(multiples)):
                unite(multiples[0], multiples[i])
        
        result = []
        for a, b in queries:
            result.append(find(a) == find(b))
        
        return result

public class Solution {
    private int[] parent;
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    private void Unite(int x, int y) {
        int px = Find(x), py = Find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
    
    public IList<bool> AreConnected(int n, int threshold, int[][] queries) {
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
        
        // 对于每个大于threshold的因子，连接其所有倍数
        for (int d = threshold + 1; d <= n; d++) {
            List<int> multiples = new List<int>();
            for (int multiple = d; multiple <= n; multiple += d) {
                multiples.Add(multiple);
            }
            
            // 连接所有倍数
            for (int i = 1; i < multiples.Count; i++) {
                Unite(multiples[0], multiples[i]);
            }
        }
        
        List<bool> result = new List<bool>();
        foreach (var query in queries) {
            result.Add(Find(query[0]) == Find(query[1]));
        }
        
        return result;
    }
}

var areConnected = function(n, threshold, queries) {
    const parent = Array.from({length: n + 1}, (_, i) => i);
    
    function find(x) {
        if (parent[x] !== x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    function union(x, y) {
        const px = find(x);
        const py = find(y);
        if (px !== py) {
            parent[px] = py;
        }
    }
    
    for (let z = threshold + 1; z <= n; z++) {
        for (let multiple = z; multiple <= n; multiple += z) {
            if (multiple !== z) {
                union(z, multiple);
            }
        }
    }
    
    return queries.map(([a, b]) => find(a) === find(b));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n + m α(n))建图需要 O(n log n)，m 次查询每次 O(α(n))
空间复杂度O(n)并查集存储空间

相关题目