We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Graph Connectivity With Threshold

Number: 1223

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

We are given n cities labeled from 1 to n. Two cities, x and y, are directly connected by a bidirectional road if and only if they share a common divisor strictly greater than a given threshold. The goal is to determine, for a list of queries, whether two given cities are connected (directly or indirectly).

Key Insights

  • Rather than connecting every pair of cities, iterate over potential common divisors (d) that are strictly greater than threshold.
  • For each divisor d (in the range threshold+1 to n), all multiples of d are guaranteed to be connected.
  • Use a Union Find (Disjoint Set Union) data structure to efficiently merge sets of cities that share a divisor.
  • After processing connections, answer each query by checking if two cities belong to the same connected component.

Space and Time Complexity

Time Complexity: O(n log n + Q * α(n))
Space Complexity: O(n)

Solution

We use the Union Find data structure to merge connected cities. For each divisor d from threshold+1 to n, iterate through its multiples and union them. Finally, for each query, we check whether the two cities have the same root (i.e., belong to the same component).

Code Solutions

Python solution:

JavaScript solution:

C++ solution:

Java solution:

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    
    def find(self, x):
        # Path compression: flattening the tree for efficiency
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

def areConnected(n, threshold, queries):
    uf = UnionFind(n + 1)  # Using 1-indexed cities
    # For each divisor greater than the threshold
    for d in range(threshold + 1, n + 1):
        # Start unioning multiples of d
        for multiple in range(2 * d, n + 1, d):
            uf.union(d, multiple)
    results = []
    for a, b in queries:
        results.append(uf.find(a) == uf.find(b))
    return results

# Example usage:
n = 6
threshold = 2
queries = [[1, 4], [2, 5], [3, 6]]
print(areConnected(n, threshold, queries))
← Back to All Questions