列表

详情

1627. 带阈值的图连通性

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

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

返回数组 answer ，其中answer.length == queries.length 。如果第 i 个查询中指向的城市 ai 和 bi 连通，则 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] 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) { } };

python3 解法, 执行用时: 136 ms, 内存消耗: 39.1 MB, 提交时间: 2023-09-28 15:18:03 

class Solution:
    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:
        if not threshold:
            return [True]*len(queries)
            
        # 并查集
        unions = list(range(n+1))
        def find(i):
            if (i!=unions[i]):
                unions[i] = find(unions[i])
                return unions[i]
            else:return i

        # 欧拉筛
        primes = []
        for t in range(threshold+1,n//2+1):
            if unions[t]==t:
                # 伪质数：
                for i in range(t*2, t*threshold+1,t):
                    # 和小于threshold的数相乘，构造低倍合数；
                    if i>n:break
                    unions[find(i)] = t 
                else:
                    for p in primes:
                        # 和小于自身的伪质数相乘，构造高倍合数
                        i = t*p
                        if i>n:break
                        unions[i] = unions[p] = t
                    else:
                        if t*t<=n:
                            primes.append(t)
                            unions[t*t] = find(t)
            else:
                # 非伪质数：
                for p in primes:
                    # 和小于自己伪质因数的伪质数相乘，构造高倍合数；
                    if t*p>n:break
                    unions[t*p] = unions[find(t)] = find(p)
                    if not t%p:break
        return [find(L)==find(R) for L,R in queries]

cpp 解法, 执行用时: 188 ms, 内存消耗: 71.2 MB, 提交时间: 2023-09-28 15:17:42 

class Solution {
public:
    int unions[10001];
    int find(int n){
        if(unions[n]!=n){
            unions[n] = find(unions[n]);
        }
        return unions[n];
    }
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        for(int i = 1; i <= n; i++){
            unions[i]=i;
        }
        for(int t = threshold+1; t <= n/2; t++){
            if (unions[t]!=t)continue;
            for(int i = t*2; i<=n; i+=t){
                unions[find(i)] = t;
            }
        }
        vector<bool>res;
        for(vector<int> ls: queries){
            res.push_back(find(ls[0])==find(ls[1]));
        }
        return res;
    }
};

python3 解法, 执行用时: 116 ms, 内存消耗: 39.3 MB, 提交时间: 2023-09-28 15:17:14 

class Solution:
    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:
        # 并查集
        unions = list(range(n+1))
        def find(i):
            if (i!=unions[i]):
                unions[i] = find(unions[i])
            return unions[i]
                
        for t in range(threshold+1,n//2+1):
            if unions[t]!=t:continue
            for i in range(t*2,n+1,t):
                unions[find(i)] = t
        return [find(L)==find(R) for L,R in queries]

java 解法, 执行用时: 10 ms, 内存消耗: 72.2 MB, 提交时间: 2023-09-28 15:16:39 

class Solution {
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
        Union u = new Union(n+1);
        for(int i = threshold+1; i <= n; i++){
            for(int j = i; j <= n; j+=i){
                u.connect(i,j);
            }
        }

        List<Boolean> ans = new ArrayList<>();
        for(int[] query:queries){
            ans.add(u.isConnect(query[0],query[1]));
        }
        return ans;
    }


    // 并查集模板
    class Union {
        int[] parents;
        int[] sizes;
        public Union(int n){
            parents = new int[n];
            for(int i = 0; i < n; i++){
                parents[i]=i;
            }

            sizes = new int[n];
            Arrays.fill(sizes,1);
        }

        private boolean isConnect(int a, int b){
            return root(a)==root(b);
        }

        public void connect(int a, int b){
            int ra = root(a);
            int rb = root(b);
            if(ra == rb) return;
            if(sizes[ra]>=sizes[rb]){
                sizes[ra]+=sizes[rb];
                parents[rb] = ra;
            }else{
                sizes[rb]+=sizes[ra];
                parents[ra] = rb;
            }
        }

        private int root(int a){
            while (parents[a] != a){
                parents[a] = root(parents[a]);
                a = parents[a];
            }
            return a;
        }
    }
}

cpp 解法, 执行用时: 136 ms, 内存消耗: 64.6 MB, 提交时间: 2023-09-28 15:15:48 

class UF {
public:
    vector<int> fa;
    vector<int> sz;
    int n;
    int comp_cnt;
    
public:
    UF(int _n): n(_n), comp_cnt(_n), fa(_n), sz(_n, 1) {
        iota(fa.begin(), fa.end(), 0);
    }
    
    int findset(int x) {
        return fa[x] == x ? x : fa[x] = findset(fa[x]);
    }
    
    void unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x != y) {
            if (sz[x] < sz[y]) {
                swap(x, y);
            }
            fa[y] = x;
            sz[x] += sz[y];
            --comp_cnt;
        }
    }
    
    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};


class Solution {
public:
    // 质数筛
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        UF uf(n + 1);
        vector<int> isPrime(n + 1, 1);
        for (int z = threshold + 1; z <= n; ++z) {
            if (isPrime[z]) {
                for (int p = z, q = z * 2; q <= n; p += z, q += z) {
                    isPrime[q] = false;
                    uf.unite(p, q);
                }
            }
        }
        
        vector<bool> ans;
        for (const auto& q: queries) {
            int x = q[0];
            int y = q[1];
            ans.push_back(uf.connected(x, y));
        }
        return ans;
    }
};

cpp 解法, 执行用时: 156 ms, 内存消耗: 64.3 MB, 提交时间: 2023-09-28 15:14:53 

class UF {
public:
    vector<int> fa;
    vector<int> sz;
    int n;
    int comp_cnt;
    
public:
    UF(int _n): n(_n), comp_cnt(_n), fa(_n), sz(_n, 1) {
        iota(fa.begin(), fa.end(), 0);
    }
    
    int findset(int x) {
        return fa[x] == x ? x : fa[x] = findset(fa[x]);
    }
    
    void unite(int x, int y) {
        x = findset(x);
        y = findset(y);
        if (x != y) {
            if (sz[x] < sz[y]) {
                swap(x, y);
            }
            fa[y] = x;
            sz[x] += sz[y];
            --comp_cnt;
        }
    }
    
    bool connected(int x, int y) {
        x = findset(x);
        y = findset(y);
        return x == y;
    }
};

class Solution {
public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        UF uf(n + 1);
        // 枚举公因数
        for (int z = threshold + 1; z <= n; ++z) {
            // 枚举两个 z 的倍数的点并连接
            for (int p = z, q = z * 2; q <= n; p += z, q += z) {
                uf.unite(p, q);
            }
        }
        
        vector<bool> ans;
        for (const auto& q: queries) {
            int x = q[0];
            int y = q[1];
            ans.push_back(uf.connected(x, y));
        }
        return ans;
    }
};

golang 解法, 执行用时: 136 ms, 内存消耗: 18.6 MB, 提交时间: 2023-09-28 15:13:43 

var un map[int]int

func areConnected(n int, threshold int, queries [][]int) []bool {
    un = map[int]int{}
    for i:=threshold+1; i<=n; i++ {
        for j:=i; j<=n; j+=i {
            a,b := find(j), find(i)
            if a != b {
                un[b] = a
            }
        }
    }
    
    re := make([]bool, len(queries))
    for k,v := range queries {
        re[k] = find(v[0]) == find(v[1])
    }
    
    return re
}
// 并查集
func find(i int) int {
    if _,ok := un[i]; !ok {
        return i
    }
    if un[i] != i {
        un[i] = find(un[i])
    }
    return un[i]
}

上一题

© 2024 leetcode.cn