🔥 LeetCode Editorial-Style Solution 🔥 | DSU + Offline Queries | 🚀 Optimized Approach
Intuition
The problem requires determining whether a path exists between two nodes with a weight limit.
A naive DFS/BFS approach would be too slow for large inp
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
- The problem requires determining whether a path exists between two nodes with a weight limit.
- A naive DFS/BFS approach would be too slow for large inputs (O(N^2) worst case).
- Disjoint Set Union (DSU) efficiently tracks connectivity between nodes, making it an ideal choice.
- We process queries in increasing order of limit and edges in increasing order of weight, ensuring efficient connectivity checks.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Sort Edges & Queries
- Sort edgeList by weight: We will only connect nodes with weight < limit for each query.
- Sort queries by limit: Ensures we only process relevant edges.
2. Process Queries Efficiently
- Maintain index i to track processed edges.
- For each query (u, v, limit), add edges where weight < limit to DSU.
- Check if u and v belong to the same component using DSU.
3. Store Results in Original Query Order
- Since queries are sorted by weight, we store their original index before sorting.
- This ensures that we return the results in the correct order.

# ⏳ Complexity Analysis
- Sorting Edges & Queries: O(E log E + Q log Q)

- Processing Queries with DSU: O(Q α(N)) (Inverse Ackermann function)

- Total Complexity: O((E + Q) log N) (Efficient for large inputs)

- Space Complexity: O(N) (For DSU arrays)



# Code
```cpp []
class disjoint{
public:

    vector<int> size,parent;
    disjoint(int n){
        size.resize(n,1);
        parent.resize(n);
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }

    int find(int node){
        if(node==parent[node]){
            return node;
        }
        return parent[node]=find(parent[node]);
    }

    void uNion(int u,int v){
        int ult_u=find(u);
        int ult_v=find(v);
        if(ult_u==ult_v){
            return ;
        }
        if(size[ult_u]<=size[ult_v]){
            parent[ult_u]=ult_v;
            size[ult_v]+=size[ult_u];
        }
        else{
            parent[ult_v]=ult_u;
            size[ult_u]+=size[ult_v];
        }
    }
};

class Solution {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        disjoint ds(n+1);
        for(int i=0;i<queries.size();i++){
            queries[i].push_back(i);
        }
        sort(edgeList.begin(),edgeList.end(),[](const vector<int>& a,const vector<int>& b){return a[2]<b[2];});
        sort(queries.begin(),queries.end(),[](const vector<int>& a,const vector<int>& b){return a[2]<b[2];});
        int i=0;
        vector<bool> res(queries.size(),false);
        for(auto& q:queries){
            while(i<edgeList.size() && edgeList[i][2]<q[2]){
                ds.uNion(edgeList[i][0],edgeList[i][1]);
                i++;
            }
            if(ds.find(q[0])==ds.find(q[1])){
                res[q[3]]=true;
            }
        }
       
        return res;
    }
};
```
['C++']