Problem Description

The Graph Connectivity With Threshold problem challenges us to analyze the connectivity of a special undirected graph. You are given two integers, n (number of nodes, labeled from 1 to n) and threshold, as well as a list of queries. Each query is a pair [u, v] asking whether nodes u and v are connected in the graph.

The graph is constructed as follows:

• There is an edge between nodes a and b if and only if gcd(a, b) > threshold, where gcd is the greatest common divisor.

Constraints:

• 1 ≤ n ≤ 10⁴
• 0 ≤ threshold < n
• 1 ≤ u, v ≤ n
• 1 ≤ queries.length ≤ 10⁵

Thought Process

At first glance, you might think about constructing the graph explicitly, checking every pair (a, b) for gcd(a, b) > threshold. However, with up to 10,000 nodes, this would mean checking up to 50 million pairs, which is far too slow.

Next, you might consider an efficient way to check connectivity, such as using a Disjoint Set Union (DSU, or Union-Find) data structure. The challenge is to build the graph efficiently without checking every possible edge.

Notice that for gcd(a, b) > threshold, both a and b must share a common factor greater than threshold. If we look at all numbers that are multiples of a given integer k (where k > threshold), then all those numbers are pairwise connected (since gcd(kx, ky) ≥ k > threshold).

This insight allows us to use the Union-Find structure to connect all multiples of each k greater than threshold, without having to check every possible pair.

Solution Approach

Let's break the solution down step-by-step:

1. Initialize Union-Find:
   • Create a DSU structure for n + 1 elements (since nodes are labeled from 1).
2. Connect Multiples:
   • For every integer k from threshold + 1 to n:
   • For every multiple m of k (i.e., m = 2k, 3k, ..., n):
   • Union k and m in the DSU.
   • This ensures all numbers sharing a factor greater than threshold are in the same connected component.
3. Answer Queries:
   • For each query [u, v], check if u and v have the same root in the DSU.
   • If so, they are connected; otherwise, not.

This approach is efficient because:

• We only process multiples for numbers greater than threshold.
• Union-Find with path compression and union by rank is very fast for connectivity queries.

Example Walkthrough

Let's take an example:
n = 6, threshold = 2, queries = [[1, 4], [2, 5], [3, 6]]

1. For k = 3:
   • Multiples of 3: 3 and 6
   • Union 3 and 6
2. For k = 4:
   • Multiples of 4: 4 only (no higher multiples ≤ 6)
3. For k = 5:
   • Multiples of 5: 5 only
4. For k = 6:
   • Multiples of 6: 6 only

Now, answer the queries:

• [1, 4]: 1 and 4 are not connected (no shared factor > 2)
• [2, 5]: 2 and 5 are not connected (gcd(2,5) = 1)
• [3, 6]: 3 and 6 are connected (gcd(3,6) = 3 > 2)

Time and Space Complexity

Brute-force approach:

• Checking all pairs for gcd(a, b) > threshold is O(n²).
• Way too slow for n up to 10⁴.

• For each k from threshold + 1 to n, we union all multiples. The total number of unions is O(n log n) (since the sum of n/k for k=1 to n is O(n log n)).
• Each query is O(α(n)), which is nearly constant due to path compression.
• Total time: O(n log n + Q), where Q is the number of queries.
• Space: O(n) for the DSU structure.

Summary

This problem is a great example of converting a seemingly complex graph construction into a manageable problem using number theory and Union-Find. The key insight is realizing that all multiples of a number greater than the threshold are inherently connected, allowing us to efficiently union groups of nodes. This approach avoids brute-force pairwise checks and leverages efficient data structures for quick connectivity queries.

Code Implementation

class DSU:
    def __init__(self, n):
        self.parent = list(range(n+1))
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py:
            self.parent[py] = px

class Solution:
    def areConnected(self, n, threshold, queries):
        dsu = DSU(n)
        for k in range(threshold+1, n+1):
            for multiple in range(2*k, n+1, k):
                dsu.union(k, multiple)
        res = []
        for u, v in queries:
            res.append(dsu.find(u) == dsu.find(v))
        return res
      

class DSU {
public:
    vector<int> parent;
    DSU(int n) {
        parent.resize(n+1);
        for (int i = 0; i <= n; ++i) parent[i] = i;
    }
    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[py] = px;
    }
};

class Solution {
public:
    vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
        DSU dsu(n);
        for (int k = threshold+1; k <= n; ++k) {
            for (int m = 2*k; m <= n; m += k) {
                dsu.unite(k, m);
            }
        }
        vector<bool> res;
        for (auto& q : queries) {
            res.push_back(dsu.find(q[0]) == dsu.find(q[1]));
        }
        return res;
    }
};
      

class DSU {
    int[] parent;
    DSU(int n) {
        parent = new int[n+1];
        for (int i = 0; i <= n; ++i) parent[i] = i;
    }
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
    void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) parent[py] = px;
    }
}

class Solution {
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
        DSU dsu = new DSU(n);
        for (int k = threshold+1; k <= n; ++k) {
            for (int m = 2*k; m <= n; m += k) {
                dsu.union(k, m);
            }
        }
        List<Boolean> res = new ArrayList<>();
        for (int[] q : queries) {
            res.add(dsu.find(q[0]) == dsu.find(q[1]));
        }
        return res;
    }
}
      

class DSU {
    constructor(n) {
        this.parent = Array(n+1).fill(0).map((_,i) => i);
    }
    find(x) {
        if (this.parent[x] !== x)
            this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        let px = this.find(x), py = this.find(y);
        if (px !== py) this.parent[py] = px;
    }
}

var areConnected = function(n, threshold, queries) {
    let dsu = new DSU(n);
    for (let k = threshold+1; k <= n; ++k) {
        for (let m = 2*k; m <= n; m += k) {
            dsu.union(k, m);
        }
    }
    let res = [];
    for (let [u, v] of queries) {
        res.push(dsu.find(u) === dsu.find(v));
    }
    return res;
};