1627

1627. Graph Connectivity With Threshold (Hard)

We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:

• x % z == 0,
• y % z == 0, and
• z > threshold.

Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly. (i.e. there is some path between them).

Return an array answer, where answer.length == queries.length and answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path.

 

Example 1:

Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
Output: [false,false,true]
Explanation: The divisors for each number:
1:   1
2:   1, 2
3:   1, 3
4:   1, 2, 4
5:   1, 5
6:   1, 2, 3, 6
Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the
only ones directly connected. The result of each query:
[1,4]   1 is not connected to 4
[2,5]   2 is not connected to 5
[3,6]   3 is connected to 6 through path 3--6

Example 2:

Input: n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
Output: [true,true,true,true,true]
Explanation: The divisors for each number are the same as the previous example. However, since the threshold is 0,
all divisors can be used. Since all numbers share 1 as a divisor, all cities are connected.

Example 3:

Input: n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]
Output: [false,false,false,false,false]
Explanation: Only cities 2 and 4 share a common divisor 2 which is strictly greater than the threshold 1, so they are the only ones directly connected.
Please notice that there can be multiple queries for the same pair of nodes [x, y], and that the query [x, y] is equivalent to the query [y, x].

 

Constraints:

• 2 <= n <= 104
• 0 <= threshold <= n
• 1 <= queries.length <= 105
• queries[i].length == 2
• 1 <= ai, bi <= cities
• ai != bi

Companies:
Trexquant

Related Topics:
Array, Math, Union Find

Solution 1. Union Find

Intuition:

1. If the GCD of two numbers is greater than threshold, use union find to connect these two numbers.
2. For each query, use union find to check if they are connected.

The brute force way is to check all the O(N^2) pairs of cities.

We need to find a way to reduce the number of pairs we need to check.

Think about the threshold value. What if threshold is very small? Then there will be lots of possible pairs. What if threshold is very large? Then there will be very few possible pairs.

Because for the minimal possible divisor d = threshold + 1, it defines a group of numbers d, 2d, 3d, 4d, ... which are inter-connected; the greater the threshold value is, the smaller such group is.

So, we can traverse all the possible divisors d = [threshold + 1, n / 2], and for each of these divisors, we connect the numbers in the same group d, 2d, 3d, 4d, ....

This is similar to Sieve of Eratosthenes.

In the worst case where threshold = 0, iterating all the city pairs cost N + N / 2 + N / 3 + ... + 1 = N * (1 + 1 / 2 + 1 / 3 + ... + 1 / N). 1 + 1 / 2 + 1 / 3 + ... + 1 / N is a Harmonic series (调和级数) and bounded by logN. So the iteration takes O(NlogN).

// OJ: https://leetcode.com/problems/graph-connectivity-with-threshold/
// Author: github.com/lzl124631x
// Time: O(NlogN + Q)
// Space: O(N)
// Ref: https://leetcode.com/problems/graph-connectivity-with-threshold/discuss/899595
class UnionFind {
    vector<int> id;
public:
    UnionFind(int n) : id(n) {
        iota(begin(id), end(id), 0);
    }
    int find(int x) {
        return id[x] == x ? x : (id[x] = find(id[x]));
    }
    void connect(int a, int b) {
        id[find(a)] = find(b);
    }
    bool connected(int a, int b) {
        return find(a) == find(b);
    }
};
class Solution {
public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& Q) {
        UnionFind uf(n + 1);
        for (int d = threshold + 1; d <= n / 2; ++d) { // Enumerate all possible common divisors
            for (int i = 2 * d; i <= n; i += d) { // Union all the numbers sharing the same divisors together
                uf.connect(d, i);
            }
        }
        vector<bool> ans;
        for (auto &q : Q) ans.push_back(uf.connected(q[0], q[1]));
        return ans;
    }
};