Checking Existence of Edge Length Limited Paths

Problem Statement

This problem involves working with an undirected graph defined by n nodes using an edgeList. Each item in edgeList consists of three elements, [ui, vi, disi], where ui and vi are node identifiers indicating an edge between them and disi represents the distance of this edge. It is important to note that there can be multiple edges between the same two nodes, each potentially having different distances.

Given a list of queries, each query [pj, qj, limitj], the task is to determine if there exists at least one path between nodes pj and qj such that every edge on this path has a distance less than limitj.

The solution should produce a boolean array answer with each element corresponding to the result of a query, where true is returned if the conditions are met for that respective query and false otherwise.

Examples

Example 1

Input:

n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]

Output:

[false,true]

Explanation:

The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2

Input:

n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]

Output:

[true,false]

Explanation:

The above figure shows the given graph.

Constraints

• 2 <= n <= 105
• 1 <= edgeList.length, queries.length <= 105
• edgeList[i].length == 3
• queries[j].length == 3
• 0 <= ui, vi, pj, qj <= n - 1
• ui != vi
• pj != qj
• 1 <= disi, limitj <= 109
• There may be multiple edges between two nodes.

Approach and Intuition

To solve this problem effectively, we must focus on both the graph's connectivity and the constraints on distances given by each query. Here's a breakdown of the steps involved:

1. Representation and Preprocessing

   • Construct an adjacency list representation of the graph using the edgeList. During this process, ensure to filter and store only those edges which might be relevant, i.e., those whose distance might be less than any limitj in the queries.

2. Pathfinding with Constraints

   • For each query, the task is to check connectivity under constraints:
     • You could use a modified Breadth-First Search (BFS) or Depth-First Search (DFS) where you only follow edges that satisfy the distance condition (< limitj).
     • An alternative and often efficient method in such 'constraint' problems is to sort both the edges and the queries by their respective distances and limits. This can leverage Union-Find (or Disjoint Set Union, DSU) structures for dynamic connectivity checks:
       • As you progress through sorted edges, you connect nodes and simultaneously handle the queries that have a limit less than the current edge's distance.

3. Efficiency Considerations

   • Sorting edges and queries might seem costly, but both operations are feasible within given constraints since they will operate at O(m log m) and O(q log q) complexities, where m is the number of edges and q is the number of queries.
   • The DSU operations (union and find) are very efficient with path compression and will generally operate near constant time for our input size.

This approach is structured to exploit sorted processing and DSU for efficient query handling without repetitively searching through the graph, thus aiming for a balance between preprocessing time and query response efficiency. This supports real-time querying even in scenarios of dense graphs and numerous queries, maintaining adherence to provided constraints.

Solutions

class DisjointSet {
public:
    vector<int> parent;
    vector<int> size;
    
    DisjointSet(int count) {
        parent = vector<int>(count);
        size = vector<int>(count, 0);
        for (int i = 0; i < count; ++i) {
            parent[i] = i;
        }
    }
    
    int find(int element) {
        if (parent[element] != element) {
            parent[element] = find(parent[element]);
        }
        return parent[element];
    }
    
    void unify(int elem1, int elem2) {
        int root1 = find(elem1);
        int root2 = find(elem2);
    
        if (root1 == root2) return;
    
        if (size[root1] > size[root2]) {
            parent[root2] = root1;
        } else if (size[root1] < size[root2]) {
            parent[root1] = root2;
        } else {
            parent[root1] = root2;
            size[root2]++;
        }
    }
    
    bool isConnected(int elem1, int elem2) {
        return find(elem1) == find(elem2);
    }
};
    
    
class Solution {
public:
    static bool edgeComparer(vector<int>& edge1, vector<int>& edge2) {
        return edge1[2] < edge2[2];
    }
    
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        DisjointSet ds(n);
        int queryLen = queries.size();
        vector<bool> results(queryLen);
    
        vector<vector<int>> indexedQueries(queryLen);
        for (int i = 0; i < queryLen; ++i) {
            indexedQueries[i] = queries[i];
            indexedQueries[i].push_back(i);
        }
    
        int currentEdge = 0;
    
        sort(edgeList.begin(), edgeList.end(), edgeComparer);
        sort(indexedQueries.begin(), indexedQueries.end(), edgeComparer);
    
        for (auto& query : indexedQueries) {
            int start = query[0];
            int end = query[1];
            int limit = query[2];
            int originalIndex = query[3];
    
            while (currentEdge < edgeList.size() && edgeList[currentEdge][2] < limit) {
                ds.unify(edgeList[currentEdge][0], edgeList[currentEdge][1]);
                currentEdge++;
            }
    
            results[originalIndex] = ds.isConnected(start, end);
        }
    
        return results;
    }
};