Graph Connectivity With Threshold
Problem
There are n cities labeled 1 to n. Two cities x and y are connected directly if they share a common divisor strictly greater than threshold. For each query [a, b], return whether cities a and b are connected (directly or indirectly).
For every divisor d > threshold, all multiples of d (d, 2d, 3d, …) share that divisor, so union them together. Then each query is just a same-root check.
n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]][false, false, true]def are_connected(n, threshold, queries):
parent = list(range(n + 1))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
parent[find(a)] = find(b)
for d in range(threshold + 1, n + 1):
multiple = 2 * d
while multiple <= n:
union(d, multiple)
multiple += d
return [find(a) == find(b) for a, b in queries]function areConnected(n, threshold, queries) {
const parent = Array.from({ length: n + 1 }, (_, i) => i);
function find(x) {
while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
function union(a, b) { parent[find(a)] = find(b); }
for (let d = threshold + 1; d <= n; d++) {
for (let m = 2 * d; m <= n; m += d) {
union(d, m);
}
}
return queries.map(([a, b]) => find(a) === find(b));
}class Solution {
int[] parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
void union(int a, int b) { parent[find(a)] = find(b); }
public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
parent = new int[n + 1];
for (int i = 0; i <= n; i++) parent[i] = i;
for (int d = threshold + 1; d <= n; d++)
for (int m = 2 * d; m <= n; m += d)
union(d, m);
List<Boolean> ans = new ArrayList<>();
for (int[] q : queries) ans.add(find(q[0]) == find(q[1]));
return ans;
}
}class Solution {
public:
vector<int> parent;
int find(int x) {
while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
return x;
}
void uni(int a, int b) { parent[find(a)] = find(b); }
vector<bool> areConnected(int n, int threshold, vector<vector<int>>& queries) {
parent.resize(n + 1);
for (int i = 0; i <= n; i++) parent[i] = i;
for (int d = threshold + 1; d <= n; d++)
for (int m = 2 * d; m <= n; m += d)
uni(d, m);
vector<bool> ans;
for (auto& q : queries) ans.push_back(find(q[0]) == find(q[1]));
return ans;
}
};Explanation
Two cities are wired together when they share a divisor greater than the threshold. Checking that directly for every pair would be slow, so we flip the view: instead of "which divisor connects this pair?", we ask "which cities does each divisor connect?".
For a fixed divisor d, every multiple of d — that is d, 2d, 3d, … — has d as a common divisor. So all those multiples belong to one connected group. We only care about divisors with d > threshold, since smaller ones do not create edges.
We loop d from threshold + 1 up to n and union d with each of its multiples 2d, 3d, …. This sieve-like double loop runs in near-linear-times-log-log time, far cheaper than testing all pairs.
After the merging, connectivity is transitive automatically through the union-find roots. Each query (a, b) is answered with a single find(a) == find(b) comparison.
Example: n = 6, threshold = 2. Divisors above 2 are 3, 4, 5, 6. Only 3 has another multiple within range (6), giving the group {3, 6}. So query (3,6) is true while (1,4) and (2,5) are false → [false, false, true].