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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Checking Existence of Edge Length Limited Paths

Difficulty: Hard

Problem Description

Given an undirected graph defined by an edge list, you need to determine whether there exists a path between two nodes such that each edge on the path has a distance strictly less than a specified limit for multiple queries.

Key Insights

  • The problem requires checking path existence under specific edge constraints.
  • Multiple edges can exist between two nodes, and their distances may vary.
  • Efficiently handling multiple queries against potentially large graphs is crucial.
  • Union-Find (Disjoint Set Union) can be used to manage connected components dynamically as edges are added based on the limits specified in the queries.

Space and Time Complexity

Time Complexity: O((E + Q) * α(N)), where E is the number of edges, Q is the number of queries, and α is the Inverse Ackermann function, which is very slow-growing.

Space Complexity: O(N + E), where N is the number of nodes and E is the number of edges.

Solution

To solve this problem, we can use a Union-Find data structure to dynamically connect nodes based on the edges whose distances are less than the limits specified in each query. The approach consists of the following steps:

  1. Sort the edges by their distances.
  2. Sort the queries based on the limit, while also keeping track of their original index.
  3. Use a Union-Find structure to connect nodes as we iterate through the sorted edges:
    • For each query, add all edges with distances less than the current query's limit to the Union-Find structure.
    • After adding edges, check if the two nodes of the query are connected.
  4. Store the result for each query and return the final results.

Code Solutions

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]

    def union(self, u, v):
        rootU = self.find(u)
        rootV = self.find(v)
        if rootU != rootV:
            if self.rank[rootU] > self.rank[rootV]:
                self.parent[rootV] = rootU
            elif self.rank[rootU] < self.rank[rootV]:
                self.parent[rootU] = rootV
            else:
                self.parent[rootV] = rootU
                self.rank[rootU] += 1

def distanceLimitedPathsExist(n, edgeList, queries):
    edgeList.sort(key=lambda x: x[2])  # Sort edges by distance
    queries = sorted(enumerate(queries), key=lambda x: x[1][2])  # Sort queries by limit
    uf = UnionFind(n)
    answer = [False] * len(queries)
    edgeIndex = 0

    for idx, (p, q, limit) in queries:
        while edgeIndex < len(edgeList) and edgeList[edgeIndex][2] < limit:
            uf.union(edgeList[edgeIndex][0], edgeList[edgeIndex][1])
            edgeIndex += 1
        answer[idx] = uf.find(p) == uf.find(q)

    return answer
← Back to All Questions