1627. Graph Connectivity With Threshold

Problem Description

In this problem, we have a total of n cities, and these cities are labeled from 1 to n. The roads between these cities are not built in a typical manner based on location or distance but rather on a numerical criterion related to the city labels. Two cities, x and y, are directly linked by a road if their labels have a common factor (divisor) greater than a given threshold. In other words, there exists an integer z greater than threshold such that both x and y are divisible by z.

We are given a list of queries, each containing a pair of cities [ai, bi]. For each query, the question is to determine whether there is a path between city ai and city bi. This path can be direct (the cities have a common factor greater than the threshold) or indirect (there is a sequence of roads connecting the two cities, possibly passing through other cities).

The goal is to return an array, indicating for each query whether a path exists (true) or does not exist (false).

Intuition

To solve this problem, we use an algorithmic technique known as Union-Find, which efficiently tracks elements grouped into disjoint sets and can quickly determine whether any two elements are in the same set. This approach is particularly useful for problems related to networking, connectivity, and clustering.

The intuition behind the solution lies in the observation that if two cities have a common divisor greater than the threshold, we can consider them to be in the same group or "connected component". Our task is to group all cities into connected components based on the given criterion. Once we have established these components, we can answer each query by simply checking if the two cities belong to the same component.

Since directly computing common divisors for every city pair would be computationally intensive, we can instead iterate over each possible divisor z that is greater than the threshold. For each z, we connect all cities that are multiples of z. In effect, we are building up the connectivity graph by progressively linking cities that have a common factor. This way, after processing all z, each connected component represents a set of cities that are all interlinked through shared divisors.

When processing the queries, we use the Union-Find data structure to quickly determine whether any two cities a and b are in the same connected component. With the connectivity graph prepared via Union-Find, each query only takes constant time to answer.

The overall solution is efficient because it systematically builds the connectivity relationship using divisors greater than the threshold and then leverages the Union-Find structure for fast query resolution.

Learn more about Union Find and Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Depth First SearchBreadth First Search

I don’t know

Solution Approach

The solution approach involves the use of the Union-Find algorithm. The main objective of using Union-Find here is to group the cities into disjoint sets where each set represents a cluster of cities that are interconnected. Below is the step-by-step walkthrough of the implementation:

Initialization of Union-Find: We first create a Union-Find data structure (represented by the UnionFind class). Each city is initially represented as a separate set (or component), as indicated by the self.p list that stores the parent for each city. The self.size list keeps track of the size of each set.
Building the connectivity graph: We iterate through every possible integer z greater than the threshold. For each such integer, we loop through the multiples of z (a), starting from threshold + 1 (since any number less than or equal to the threshold shouldn't be connected according to the problem statement). For each multiple a, we find other multiples b (where b starts from a + a to avoid redundant pairs and counting a itself) and union the sets that a and b belong to. The union function is responsible for merging sets, ensuring that if a is connected to b, all cities connected to a are now considered connected to b as well.
Answering the queries: Once the connectivity graph is established, we answer the queries. For each query [ai, bi], we check if cities ai and bi are in the same set by comparing their ultimate parents in the Union-Find structure. If their parents are the same, they share a connection, directly or indirectly, and hence we return true. Otherwise, we return false.

The strength of the solution is due to the way Union-Find efficiently combines sets and checks for connectivity. The find function is optimized with path compression, making subsequent searches for the same element faster. The union function also performs union by size (sometimes known as union by rank), ensuring that the tree representing a set remains as flat as possible to minimize the depth of searches.

Correctly utilized, this results in a solution that is highly efficient in terms of both time and space complexity, enabling it to solve even large-scale connectivity problems with many elements and connections.

The process of finding common divisors and union operations ensures that all cities that could possibly share a path based on the rules of the problem are placed in the same connected component, which allows for efficient query responses regarding their connectivity.

This approach works since we deal with the numbers (city labels) themselves and the commonalities between these numbers in the context of their divisors, enabling a numerical and algebraic solution to what could otherwise be approached as a graph connectivity problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Example Walkthrough

Let's consider a simple scenario where we have n = 6 cities, labeled from 1 to 6, and we set our threshold to 2. Therefore, two cities will be connected if they share a common factor (divisor) greater than 2.

Now, let's process our city connectivity using the Union-Find algorithm according to the Solution Approach described above:

Initialization of Union-Find: We have an array of n city slots representing each city as a separate 'parent', simulating the initial separate sets for each city. For simplicity, this can be represented as parents = [1, 2, 3, 4, 5, 6], where the index represents the city, and the value at each index represents its current set parent.
Building the connectivity graph: We iterate through integers greater than 2, i.e., z = 3, 4, 5, 6, .... We start connecting cities based on these multiples.
- For z = 3, we find cities 3 and 6 as multiples. We perform the union operation for cities 3 and 6.
- For z = 4, 4 is in its own set, so no operation is needed here since there are no other multiples less or equal to 6.
- We continue for z = 5 and z = 6, but since no other multiples exist within our city range, no further union operations are performed.
After the iteration, we might end up with parents array resembling something like parents = [1, 2, 3, 4, 5, 3], which implies city 6 now has 3 as its parent, meaning they belong to the same set.
Answering the queries: Suppose we have queries [[1, 4], [4, 5], [3, 6]] that ask if there's a connection between the pairs of cities:
- For [1, 4], they do not have a common parent, so they are not connected (result: false).
- For [4, 5], they do not have a common parent either, so they are not connected (result: false).
- For [3, 6], they both share a common parent of 3 (because we united them earlier based on being multiples of 3), so they are connected (result: true).

By utilizing Union-Find with these steps, we efficiently grouped cities into subsets based on their shared factors above the threshold and swiftly answered queries about their connectivity. The resulting array of answers for our queries case would be [false, false, true].

Solution Implementation

1from typing import List
2
3
4class UnionFind:
5    def __init__(self, size: int):
6        # Initialize the parents to point to themselves and set the size of each set to 1
7        self.parent = list(range(size))
8        self.set_size = [1] * size
9
10    def find(self, node: int) -> int:
11        # Find the root of the node with path compression
12        if self.parent[node] != node:
13            self.parent[node] = self.find(self.parent[node])
14        return self.parent[node]
15
16    def union(self, node1: int, node2: int) -> bool:
17        # Union the sets containing node1 and node2
18        root1, root2 = self.find(node1), self.find(node2)
19
20        # If both nodes have the same root, they are already connected
21        if root1 == root2:
22            return False
23
24        # Attach the smaller set to the root of the larger set
25        if self.set_size[root1] > self.set_size[root2]:
26            self.parent[root2] = root1
27            self.set_size[root1] += self.set_size[root2]
28        else:
29            self.parent[root1] = root2
30            self.set_size[root2] += self.set_size[root1]
31
32        # The union was successful
33        return True
34
35
36class Solution:
37    def are_connected(
38            self, nodes_count: int, threshold: int, queries: List[List[int]]
39    ) -> List[bool]:
40        # Initialize UnionFind with one extra space for 1-based indexing
41        uf = UnionFind(nodes_count + 1)
42
43        # Only consider numbers greater than the threshold for union
44        for a in range(threshold + 1, nodes_count + 1):
45            # Union multiples of a
46            for b in range(2 * a, nodes_count + 1, a):
47                uf.union(a, b)
48
49        # Process each query to check if two nodes are connected
50        return [uf.find(node1) == uf.find(node2) for node1, node2 in queries]
51
52
53# You can test the functionality by creating an instance of Solution and calling
54# the are_connected method with appropriate arguments.
55

1class UnionFind {
2    private int[] parent; // Parent array to store the representative element for each set
3    private int[] size; // Array to store the size of each set
4
5    public UnionFind(int n) {
6        parent = new int[n];
7        size = new int[n];
8        // Initialize each element to be a self-parent (own set) with size 1
9        for (int i = 0; i < n; ++i) {
10            parent[i] = i;
11            size[i] = 1;
12        }
13    }
14
15    // Find the representative of the set to which 'x' belongs
16    public int find(int x) {
17        if (parent[x] != x) {
18            // Path compression, pointing the current element directly to the representative
19            parent[x] = find(parent[x]);
20        }
21        return parent[x];
22    }
23
24    // Merge the sets containing 'a' and 'b'
25    public boolean union(int a, int b) {
26        int parentA = find(a), parentB = find(b);
27      
28        // Return false if both elements are already in the same set
29        if (parentA == parentB) {
30            return false;
31        }
32      
33        // Weighed union: attach the smaller tree to the root of the larger tree
34        if (size[parentA] > size[parentB]) {
35            parent[parentB] = parentA;
36            size[parentA] += size[parentB];
37        } else {
38            parent[parentA] = parentB;
39            size[parentB] += size[parentA];
40        }
41        return true; // Return true as the union was successful
42    }
43}
44
45class Solution {
46    public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
47        UnionFind uf = new UnionFind(n + 1); // Create a union-find for 'n' elements
48
49        // Start from 'threshold + 1' and connect all multiples
50        for (int a = threshold + 1; a <= n; ++a) {
51            for (int b = a + a; b <= n; b += a) {
52                uf.union(a, b); // Union sets containing 'a' and 'b'
53            }
54        }
55
56        List<Boolean> ans = new ArrayList<>(); // List to store the answer for each query
57        for (int[] query : queries) {
58            // Check if 'query[0]' and 'query[1]' have the same representative
59            ans.add(uf.find(query[0]) == uf.find(query[1]));
60        }
61
62        return ans; // Return the list containing query results
63    }
64}
65

1#include <vector>
2#include <numeric>
3
4class UnionFind {
5public:
6    // Constructor initializes two vectors, one for storing parent references, and another for size of each set
7    UnionFind(int n) {
8        parents = std::vector<int>(n);
9        sizes = std::vector<int>(n, 1);
10
11        // Fill the parents vector so that each element is initially its own parent
12        std::iota(parents.begin(), parents.end(), 0);
13    }
14
15    // Unite two sets; if they are already connected return false, otherwise unite and return true
16    bool unite(int a, int b) {
17        int parentA = find(a), parentB = find(b);
18
19        // Check if both elements have the same parent
20        if (parentA == parentB) {
21            return false;
22        }
23
24        // Union by size: attach the smaller tree to the root of the larger tree
25        if (sizes[parentA] > sizes[parentB]) {
26            parents[parentB] = parentA;
27            sizes[parentA] += sizes[parentB];
28        } else {
29            parents[parentA] = parentB;
30            sizes[parentB] += sizes[parentA];
31        }
32
33        return true;
34    }
35
36    // Find the root parent of a given element, with path compression
37    int find(int x) {
38        // Path compression: Make each looked-up element point to the root directly
39        if (parents[x] != x) {
40            parents[x] = find(parents[x]);
41        }
42
43        return parents[x];
44    }
45
46private:
47    std::vector<int> parents; // Vector to store the parent of each element
48    std::vector<int> sizes; // Vector to store the size of each set (only valid for root elements)
49};
50
51class Solution {
52public:
53    // Method to determine if the given queries are connected considering a certain threshold
54    std::vector<bool> areConnected(int n, int threshold, std::vector<std::vector<int>>& queries) {
55        UnionFind uf(n + 1);
56
57        // Connect nodes which are multiples of each number greater than the threshold
58        for (int a = threshold + 1; a <= n; ++a) {
59            for (int b = 2 * a; b <= n; b += a) {
60                uf.unite(a, b);
61            }
62        }
63
64        std::vector<bool> answers; // This will hold the final answers to queries
65
66        // For each query, check if the two queried numbers are connected
67        for (auto& query : queries) {
68            bool isConnected = uf.find(query[0]) == uf.find(query[1]);
69            answers.push_back(isConnected);
70        }
71
72        return answers;
73    }
74};
75

1// Global variables representing the disjoint set data structure
2const parent: number[] = [];
3const setSize: number[] = [];
4
5// Initializes the disjoint set data structure with `n` elements
6function initializeUnionFind(n: number): void {
7    for (let i = 0; i <= n; i++) {
8        parent[i] = i;
9        setSize[i] = 1;
10    }
11}
12
13// Returns the root of the set that element `x` belongs to
14function find(x: number): number {
15    if (parent[x] !== x) {
16        parent[x] = find(parent[x]); // Path compression
17    }
18    return parent[x];
19}
20
21// Merges the sets to which elements `a` and `b` belong, and
22// returns true if a merge happened, false if already connected
23function union(a: number, b: number): boolean {
24    let rootA = find(a);
25    let rootB = find(b);
26
27    if (rootA === rootB) {
28        return false; // Already in the same set
29    }
30
31    // Union by size: attach the smaller tree to the root of the larger tree
32    if (setSize[rootA] > setSize[rootB]) {
33        parent[rootB] = rootA;
34        setSize[rootA] += setSize[rootB];
35    } else {
36        parent[rootA] = rootB;
37        setSize[rootB] += setSize[rootA];
38    }
39    return true;
40}
41
42// Determines if nodes `a` and `b` are connected for each query in `queries`
43function areConnected(n: number, threshold: number, queries: number[][]): boolean[] {
44    initializeUnionFind(n); // Initialize for n+1 elements (0 through n inclusive)
45
46    // Connect all multiples of each number starting from `threshold + 1` through `n`
47    for (let a = threshold + 1; a <= n; ++a) {
48        for (let b = a * 2; b <= n; b += a) {
49            union(a, b); // Union multiples of `a`
50        }
51    }
52
53    // For each query, check if the elements are connected
54    return queries.map(([a, b]) => find(a) === find(b));
55}
56

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Time and Space Complexity

The time complexity of the UnionFind operations is O(α(n)), where α is the inverse Ackermann function, which is nearly constant for all practical values of n. The initialization of the UnionFind instance is O(n) since it requires initializing two lists of size n.

In the areConnected function, we start iterating through each number a from threshold + 1 to n. For each a, we iterate through its multiples b, starting from a + a to n with a step of a. There would be approximately n / a multiples of a to consider, and since the union operation is performed for each multiple, the complexity for iterating through multiples of a would be O((n / a) * α(n)). Summing this over all numbers from threshold + 1 to n, the complexity approximates Σ(n / a) from a = threshold + 1 to n, which is roughly O(n * log(n)), as this is a harmonic series which can be bounded by the logarithm.

When considering the queries, each query involves two find operations, leading to a complexity of O(q * α(n)), where q is the number of queries.

The overall time complexity, which combines the complexity of initializing the UnionFind, iterating over the numbers and their multiples, and processing the queries, is O(n + n * log(n) * α(n) + q * α(n)), simplifying to O(n * log(n) * α(n) + q * α(n)).

The space complexity is O(n) due to the storage requirements of the UnionFind data structure, which needs to store the parent and size for each of the n nodes.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

O(1)O(n)O(n!)O(n^n)

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1627. Graph Connectivity With Threshold

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings