带阈值的图连通性

难度: Hard

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

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

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

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

示例 1：

输入：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：

输入：n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
输出：[true,true,true,true,true]
解释：每个数的因数与上一个例子相同。但是，由于阈值为 0 ，所有的因数都大于阈值。因为所有的数字共享公因数 1 ，所以所有的城市都互相连通。

示例 3：

输入：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⁴
0 <= threshold <= n
1 <= queries.length <= 10⁵
queries[i].length == 2
1 <= a_i, b_i <= cities
a_i != b_i

Submission

运行时间: 88 ms

内存: 39.2 MB

class Solution:
    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:

        if not threshold: #任意两个自然数都有公约数1，这种情况一定都是True
            return [True]*len(queries)

        def find(index: int) -> int: #并查集模板
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)

        parent = list(range(n+1))
        out = set() #out表示已出局，out里的数的倍数是已经遍历合并过的

        for p in range(threshold+1,n+1):
            if p not in out:
                num = 2*p #一定要从2*p开始！不要因为担心TLE而从p*p开始，从p*p开始只要p不是素数就会漏合并！
                while num<=n: #注意超过n的数于本题没有意义，及时退出循环
                    union(num,p)
                    out.add(num)  # num不是素数，也有超过threshold的因子，以后遇到num就跳过
                    num+=p
        
        return [find(x)==find(y) for x,y in queries] #预处理结束，依次查询就得到答案

Explain

该题解采用了并查集的思想来判断城市之间的连通性。首先，特判当阈值为0时，任意两个自然数都有公约数1，因此所有城市都连通。然后，使用并查集的方法，将每个城市初始化为独立的集合。接着，从阈值+1开始遍历到n，对于每个数p，遍历其所有大于阈值的倍数，并将这些倍数与p进行合并，表示它们之间是连通的。最后，对于每个查询，判断两个城市是否属于同一个集合，即可得到它们是否连通。

时间复杂度: O(nlogn + mlogn)

空间复杂度: O(n)

class Solution:
    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:

        if not threshold: # 任意两个自然数都有公约数1，这种情况一定都是True
            return [True]*len(queries)

        def find(index: int) -> int: # 并查集查找操作
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int): # 并查集合并操作
            parent[find(index1)] = find(index2)

        parent = list(range(n+1)) # 初始化并查集
        out = set() # out表示已出局，out里的数的倍数是已经遍历合并过的

        for p in range(threshold+1,n+1):
            if p not in out:
                num = 2*p # 从2*p开始遍历p的倍数
                while num<=n: # 注意超过n的数于本题没有意义，及时退出循环
                    union(num,p)
                    out.add(num)  # 将已合并的数加入out集合
                    num+=p
        
        return [find(x)==find(y) for x,y in queries] # 预处理结束，依次查询就得到答案

Explore

当阈值为0时，任意两个自然数至少有1作为公共因数，因此任意两个城市之间都可以认为是连通的。在数学上，所有非零整数都至少有1这个共同的因数，所以不论怎样选择两个城市，它们都至少通过1这个公共因数连接起来，符合题目中的连通性定义。

从阈值+1到n之间的数被选择是因为，如果我们考虑阈值以下的数（包括阈值本身），这些数的任何倍数都会小于或等于阈值，因此不会成为两个大于阈值的数的公共因子。因此，只有当我们从阈值+1开始考虑时，我们才开始处理能够成为大于阈值数的有效公共因子。这样可以避免处理无效的连接（即那些不满足阈值要求的连接）。

并查集通过维持每个元素的父指针来管理不同集合的归属关系。初始化时，每个城市指向自己，表示它们各自是一个独立的集合。在处理过程中，通过合并操作（union），如果两个城市通过某个公共因子连通，则这两个城市或其相关连的城市会被合并到同一个集合中。这种方法确保了只要有连通路径存在，相关城市最终都会属于同一个集合，从而正确处理连通性问题。

并查集的合并操作通过遍历每个大于阈值的数的倍数来实施。对于每个数p，它的所有倍数（大于阈值且小于等于n的）都会与p合并，这确保了所有因共同因子（倍数关系）而连通的城市都被合并到同一集合。虽然这个方法有效地覆盖了大多数场景，但理论上如果处理不当（如遍历不完全或阈值处理错误），可能会遗漏一些连接。然而，按照题解的逻辑，只要正确实施并查集的操作并完全遍历，就应该能够确保所有必要的连通性都被正确处理。