1627. Graph Connectivity With Threshold

The problem is called "Graph Connectivity With Threshold" and it's about a group of cities that are connected via bidirectional roads only if they share a common divisor that is strictly greater than a given threshold. We are given the number of cities, a threshold, and an array of queries. Each query consists of two cities and we need to determine if there is a path between them.

Consider n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]].

Each number from 1 to n (6) has certain divisors and only divisors above the threshold (2) are considered. For each pair of cities in queries, we need to check if they share a common divisor that's strictly greater than the threshold. In this case, only cities 3 and 6 share a common divisor (3) which is greater than the threshold, meaning they are connected.

The solution revolves around a technique called "Union Find" or "Disjoint Set Union" (DSU). Union Find is a data structure that helps to check if an element is in the same group or not, and merge 2 groups together. The implementation of UnionFind consists of an ID and Rank array, and the three main operations are Union, Find, and Union By Rank.

Using this solution, connections between any two cities a and b are established only if there exists an integer z such that a and b are both divisible by z and z is strictly greater than the threshold. All numbers from the threshold plus 1 up to n are iterated over as potential z values and for each z, connections are established with multiples of z in the range to n.

Finally, for each query, the solution employs the find method that determines if the two cities belong to the same set, i.e., if they are connected.

Python

1
2python
3class DSU:
4    def __init__(self, n):
5        self.p = list(range(n+1))
6
7    def union(self, x, y):
8        self.p[self.find(x)] = self.find(y)
9
10    def find(self, x):
11        if self.p[x] != x:
12            self.p[x] = self.find(self.p[x])
13        return self.p[x]
14
15class Solution:
16    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:
17        dsu = DSU(n)
18
19        for i in range(threshold+1, n+1):
20            for j in range(i+i, n+1, i):
21                dsu.union(i, j)
22
23        return [dsu.find(x) == dsu.find(y) for x, y in queries]

Java

1
2java
3class Solution {
4    int[] parent;
5
6    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
7        parent = new int[n + 1];
8        for (int i = 0; i <= n; i++)
9            parent[i] = i;
10    
11        for (int i = threshold + 1; i <= n; i++)
12            for (int j = 2 * i; j <= n; j += i)
13                parent[find(i)] = find(j);
14            
15        List<Boolean> list = new ArrayList<>();
16        for (int[] query : queries) 
17            list.add(find(query[0]) == find(query[1]));
18            
19        return list;
20    }
21    
22    int find(int x) {
23        if (x != parent[x]) parent[x] = find(parent[x]);
24        return parent[x];
25    }
26}

JavaScript

1
2javascript
3class Solution {
4    constructor(n) {
5        this.parent = Array.from({length: n+1}, (_, i) => i);
6    }
7
8    union(x, y) {
9        this.parent[this.find(x)] = this.find(y);
10    }
11
12    find(x) {
13        if (this.parent[x] !== x) 
14            this.parent[x] = this.find(this.parent[x]);
15        return this.parent[x];
16    }
17
18    areConnected(n, threshold, queries) {
19        for (let i = threshold + 1; i <= n; ++i)
20            for (let j = 2 * i; j <= n; j += i)
21                this.union(i, j);
22
23        return queries.map(([x, y]) => this.find(x) === this.find(y));
24    }
25}

In conclusion, by utilizing the Disjoint Set Union (DSU) or Union-Find data structure, we can effectively solve the "Graph Connectivity with Threshold" problem. This data structure makes it easy to check if two cities belong to the same group (connected) and merge groups together if they share a common divisor above the threshold.

In Python, we utilize list comprehension for a more concise and compact implementation. Java solution features the same underlying logic, although without the concise syntax of Python. JavaScript implementation is similar to Python's but leverages JavaScript's native map function as well as dynamic array creation and value assignment.

These solutions highlight the power and versatility of the DSU data structure--it's not only used for this particular graph connectivity problem, but also a common tool for many other problems involving the manipulation and management of data grouped into sets. DSU is indeed a potent tool to have in your problem-solving arsenal!

Remember, practice is key in mastering these concepts. Try implementing these solutions and test with different cases to understand the working of the Union-find data structure. Happy coding!