# Graph Connectivity With Threshold
**Difficulty:** HARD
[External](https://leetcode.com/problems/graph-connectivity-with-threshold)
Canonical: https://scaleengineer.com/dsa/problems/graph-connectivity-with-threshold
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array
---
## Problem
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:**

![](https://assets.glich.co/dsa/graph-connectivity-with-threshold/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/graph-connectivity-with-threshold/image1.jpg) 

**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:**

![](https://assets.glich.co/dsa/graph-connectivity-with-threshold/image2.jpg) 

**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`

# Approaches
## Brute-Force Graph Traversal
This is the most naive approach. First, an explicit graph is constructed by checking every pair of cities for a direct connection. An adjacency list is used to store the graph. Then, for each query, a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) is run to check for a path between the two cities.
**Time:** O(n^3 + Q * (n + E)), where `n` is the number of cities, `Q` is the number of queries, and `E` is the number of edges. In the worst case, `E` can be `O(n^2)`. The graph construction takes `O(n^3)` and each of the `Q` queries takes `O(n+E)`. This is prohibitively slow. · **Space:** O(n + E), where E is the number of edges. In the worst case, E can be O(n^2), so the space complexity is O(n^2).
**Pros:** Very straightforward and easy to understand for those familiar with basic graph algorithms.
**Cons:** Extremely inefficient due to the O(n^3) graph construction time.; Query processing is also slow, as it repeats traversal work for each query.; The space complexity for the adjacency list can be large, up to O(n^2).; Guaranteed to result in Time Limit Exceeded for the given constraints.
### Explanation
This method separates the problem into two distinct phases: graph building and path finding.

**Graph Building:**
1.  Create an adjacency list, `adj`, to represent the graph, where `adj[i]` stores the neighbors of city `i`.
2.  Iterate through all pairs of cities `(i, j)` with `1 <= i < j <= n`.
3.  For each pair, check if they share a common divisor `z > threshold`. This can be done by iterating `z` from `threshold + 1` to `i`.
4.  If such a `z` is found, add an edge between `i` and `j` in the adjacency list (i.e., add `j` to `adj[i]` and `i` to `adj[j]`).

**Query Processing:**
1.  For each query `[a, b]`, perform a traversal (e.g., BFS) starting from city `a`.
2.  Use a `visited` array to keep track of visited nodes during the traversal.
3.  If city `b` is reached during the traversal, the cities are connected.
4.  If the traversal completes without reaching `b`, they are not connected.

This approach is highly inefficient because it rebuilds the path-finding work for every single query.

```java
import java.util.*;

class Solution {
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
        // 1. Graph Building
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        if (threshold == 0) {
            List<Boolean> allConnected = new ArrayList<>();
            for (int i = 0; i < queries.length; i++) allConnected.add(true);
            return allConnected;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                for (int z = threshold + 1; z <= i; z++) {
                    if (i % z == 0 && j % z == 0) {
                        adj.get(i).add(j);
                        adj.get(j).add(i);
                        break;
                    }
                }
            }
        }

        // 2. Query Processing
        List<Boolean> result = new ArrayList<>();
        for (int[] query : queries) {
            result.add(hasPath(query[0], query[1], n, adj));
        }
        return result;
    }

    private boolean hasPath(int start, int end, int n, List<List<Integer>> adj) {
        if (start == end) return true;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];

        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            if (curr == end) return true;

            for (int neighbor : adj.get(curr)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        return false;
    }
}
```
### Algorithm
*   `1. Create an adjacency list `adj` of size `n+1` to represent the graph.`
*   `2. For each integer `i` from `1` to `n`:`
*   `   a. For each integer `j` from `i + 1` to `n`:`
*   `      i. Iterate `z` from `threshold + 1` to `i`.`
*   `      ii. If `i % z == 0` and `j % z == 0`, an edge exists. Add `j` to `adj[i]` and `i` to `adj[j]`, then break the inner loop.`
*   `3. Initialize an empty list `answer` to store query results.`
*   `4. For each query `[a, b]` in `queries`:`
*   `   a. Perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from `a` to check if `b` is reachable.`
*   `   b. Add `true` to `answer` if a path is found, otherwise add `false`.`
*   `5. Return the `answer` list.`

## Pairwise City Comparison with Union-Find
This approach iterates through all possible pairs of cities `(i, j)`. For each pair, it checks if they are directly connected by finding a common divisor `z` greater than the `threshold`. If they are, it uses a Disjoint Set Union (DSU) data structure to merge their components. After checking all pairs, the DSU structure contains all connectivity information, allowing for fast query processing.
**Time:** O(n^3 * α(n) + Q * α(n)). The construction phase iterates through O(n^2) pairs, and for each pair, it may check up to O(n) divisors. Each union operation takes O(α(n)) time. The query part is fast, but the construction is the bottleneck. · **Space:** O(n) to store the parent and size arrays for the DSU data structure.
**Pros:** Conceptually simpler than the most optimal approach.; Efficiently handles queries once the DSU structure is built, with nearly constant time per query.
**Cons:** The graph construction phase is very slow, with a time complexity of O(n^3) in the worst case.; Will result in Time Limit Exceeded for the given constraints.
### Explanation
This method improves upon a pure brute-force approach by using a DSU to efficiently handle the transitive nature of connectivity. Instead of running a graph traversal for each query, we pre-compute all connected components.

The algorithm is as follows:
1.  Initialize a DSU structure for `n+1` elements.
2.  Iterate through every pair of distinct cities `(i, j)` where `1 <= i < j <= n`.
3.  For each pair, determine if they are directly connected. This is done by checking for a common divisor `z > threshold`. A simple way to do this is to iterate `z` from `threshold + 1` to `i` (since `i < j`).
4.  If a `z` is found such that `i % z == 0` and `j % z == 0`, it means cities `i` and `j` are directly connected. We then perform `union(i, j)` and can stop checking other divisors for this pair.
5.  After iterating through all pairs, the DSU is fully built.
6.  Process each query `[a, b]` by checking if `find(a) == find(b)`.

The main drawback is the `O(n^2)` pairs to check, and for each pair, we might do up to `O(n)` work, leading to a high time complexity for the graph construction phase.

```java
import java.util.*;

class DSU {
    private int[] parent;
    private int[] size;
    public DSU(int n) {
        parent = new int[n + 1];
        size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    public int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            if (size[rootI] < size[rootJ]) {
                parent[rootI] = rootJ;
                size[rootJ] += size[rootI];
            } else {
                parent[rootJ] = rootI;
                size[rootI] += size[rootJ];
            }
        }
    }
}

class Solution {
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
        if (threshold == 0) {
            List<Boolean> allConnected = new ArrayList<>();
            for (int i = 0; i < queries.length; i++) allConnected.add(true);
            return allConnected;
        }

        DSU dsu = new DSU(n);

        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                for (int z = threshold + 1; z <= i; z++) {
                    if (i % z == 0 && j % z == 0) {
                        dsu.union(i, j);
                        break;
                    }
                }
            }
        }

        List<Boolean> result = new ArrayList<>();
        for (int[] query : queries) {
            result.add(dsu.find(query[0]) == dsu.find(query[1]));
        }
        return result;
    }
}
```
### Algorithm
*   `1. Create a Disjoint Set Union (DSU) data structure for `n+1` elements.`
*   `2. For each integer `i` from `1` to `n`:`
*   `   a. For each integer `j` from `i + 1` to `n`:`
*   `      i. Check if there exists a common divisor `z > threshold` for `i` and `j`.`
*   `      ii. If such a `z` exists, perform `union(i, j)` and break the inner check.`
*   `3. Initialize an empty list `answer`.`
*   `4. For each query `[a, b]` in `queries`:`
*   `   a. Check if `find(a)` is equal to `find(b)`.`
*   `   b. Add the result to the `answer` list.`
*   `5. Return the `answer` list.`

## Sieve-like Approach with Union-Find
This approach avoids building an explicit graph or checking all pairs of cities. Instead, it iterates through all possible common divisors `z` greater than the threshold. For each such `z`, it identifies all its multiples up to `n` and unifies them into a single connected component using a Disjoint Set Union (DSU) data structure. This is efficient because the total number of union operations is related to the harmonic series, resulting in an `O(n log n)` complexity for building the connectivity information.
**Time:** O(n * log(n) * α(n) + Q * α(n)), where `n` is the number of cities, `Q` is the number of queries, and `α(n)` is the inverse Ackermann function (a very slowly growing function, effectively constant). The `n * log(n)` part comes from iterating through divisors and their multiples (related to the harmonic series sum), and each union/find operation takes `α(n)` time. · **Space:** O(n) to store the parent and size arrays for the DSU data structure.
**Pros:** Very efficient for building the connectivity information, with a time complexity of O(n log n).; Query processing is nearly constant time per query, making it suitable for a large number of queries.; Space complexity is linear, O(n), which is optimal.
**Cons:** Requires understanding of the Disjoint Set Union data structure.; The logic is less direct than a brute-force check, involving a shift in perspective from checking city pairs to checking common divisors.
### Explanation
The core idea is to realize that if two numbers `a` and `b` are multiples of `z`, they are connected (if `z > threshold`). By extension, all multiples of `z` are mutually connected and belong to the same component.

We can use a Union-Find (or DSU) data structure to efficiently manage these connected components. The DSU will have `n+1` elements, representing cities `1` to `n`.

The algorithm proceeds as follows:
1.  Initialize a DSU structure for `n+1` elements, where each city is in its own set.
2.  Iterate through each integer `z` from `threshold + 1` up to `n`. This `z` will be our potential common divisor.
3.  For each `z`, iterate through its multiples: `2*z, 3*z, 4*z, ...` up to `n`.
4.  For each multiple `m = k*z`, we know that `z` is a common divisor of `z` and `m`. Since `z > threshold`, cities `z` and `m` are connected. We perform a `union(z, m)` operation. This effectively groups all multiples of `z` into the same set.
5.  After iterating through all possible `z` values, the DSU structure will accurately represent the connectivity of all cities.
6.  Finally, process the `queries`. For each query `[a, b]`, we check if `a` and `b` are in the same set by comparing their roots: `find(a) == find(b)`. If they are, the cities are connected; otherwise, they are not.

This method is much faster than pairwise checks because the total number of operations in the nested loops is `sum_{z=threshold+1 to n} (n/z)`, which is bounded by `n * sum_{z=1 to n} (1/z) ≈ n * log(n)`.

```java
import java.util.*;

class DSU {
    private int[] parent;
    private int[] size;
    public DSU(int n) {
        parent = new int[n + 1];
        size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    public int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            if (size[rootI] < size[rootJ]) {
                parent[rootI] = rootJ;
                size[rootJ] += size[rootI];
            } else {
                parent[rootJ] = rootI;
                size[rootI] += size[rootJ];
            }
        }
    }
}

class Solution {
    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
        if (threshold == 0) {
            List<Boolean> allConnected = new ArrayList<>();
            for (int i = 0; i < queries.length; i++) allConnected.add(true);
            return allConnected;
        }

        DSU dsu = new DSU(n);

        for (int z = threshold + 1; z <= n; z++) {
            for (int m = 2 * z; m <= n; m += z) {
                dsu.union(z, m);
            }
        }

        List<Boolean> result = new ArrayList<>();
        for (int[] query : queries) {
            int u = query[0];
            int v = query[1];
            result.add(dsu.find(u) == dsu.find(v));
        }
        return result;
    }
}
```
### Algorithm
*   `1. Create a Disjoint Set Union (DSU) data structure for `n+1` elements.`
*   `2. For each integer `z` from `threshold + 1` to `n`:`
*   `   a. For each multiple `m` of `z` (i.e., `2*z, 3*z, ...`) that is less than or equal to `n`:`
*   `      i. Perform `union(z, m)` to connect city `z` and city `m`.`
*   `3. Initialize an empty list `answer` to store results.`
*   `4. For each query `[a, b]` in `queries`:`
*   `   a. Check if `find(a)` is equal to `find(b)`.`
*   `   b. Add the result (`true` or `false`) to the `answer` list.`
*   `5. Return the `answer` list.`

# Solutions
### Java

```java
class UnionFind { private int [] p ; private int [] size ; public UnionFind ( int n ) { p = new int [ n ]; size = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; size [ i ] = 1 ; } } public int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } public boolean union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } } class Solution { public List < Boolean > areConnected ( int n , int threshold , int [][] queries ) { UnionFind uf = new UnionFind ( n + 1 ); for ( int a = threshold + 1 ; a <= n ; ++ a ) { for ( int b = a + a ; b <= n ; b += a ) { uf . union ( a , b ); } } List < Boolean > ans = new ArrayList <>(); for ( var q : queries ) { ans . add ( uf . find ( q [ 0 ]) == uf . find ( q [ 1 ])); } return ans ; } }
```

### CPP

```cpp
class UnionFind { public: UnionFind ( int n ) { p = vector < int > ( n ); size = vector < int > ( n , 1 ); iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } private: vector < int > p , size ; }; class Solution { public: vector < bool > areConnected ( int n , int threshold , vector < vector < int >>& queries ) { UnionFind uf ( n + 1 ); for ( int a = threshold + 1 ; a <= n ; ++ a ) { for ( int b = a + a ; b <= n ; b += a ) { uf . unite ( a , b ); } } vector < bool > ans ; for ( auto & q : queries ) { ans . push_back ( uf . find ( q [ 0 ]) == uf . find ( q [ 1 ])); } return ans ; } };
```

### Python

```python
class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) self . size = [ 1 ] * n def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] def union ( self , a , b ): pa , pb = self . find ( a ), self . find ( b ) if pa == pb : return False if self . size [ pa ] > self . size [ pb ]: self . p [ pb ] = pa self . size [ pa ] += self . size [ pb ] else : self . p [ pa ] = pb self . size [ pb ] += self . size [ pa ] return True class Solution : def areConnected ( self , n : int , threshold : int , queries : List [ List [ int ]] ) -> List [ bool ]: uf = UnionFind ( n + 1 ) for a in range ( threshold + 1 , n + 1 ): for b in range ( a + a , n + 1 , a ): uf . union ( a , b ) return [ uf . find ( a ) == uf . find ( b ) for a , b in queries ]
```