1697. Checking Existence of Edge Length Limited Paths

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.

class Solution {
    int getParent(vector<int>& g, int n) {
        return g[n] == n ? n : getParent(g, g[n]);
    }
    void merge(vector<int>& g, int a, int b) {
        int pa = getParent(g,a);
        int pb = getParent(g,b);

        if(pa > pb) swap(pa, pb);
        g[pa] = g[pb] = pa;
    }
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& e, vector<vector<int>>& q) {
        map<int, vector<vector<int>>> m;
        vector<int> gr(n);
        vector<bool> res(q.size());
        for(int i = 0; i < n; i++) gr[i] = i;
        for(int i = 0; i < q.size(); i++) {
            m[q[i][2]].push_back({q[i][0],q[i][1],i});
        }
        int ePos = 0;
        sort(e.begin(), e.end(), [](auto& a, auto& b) { return a[2] < b[2]; });
        for(auto& qrs : m) {
            for(; ePos < e.size() and e[ePos][2] < qrs.first; ePos++) {
                merge(gr, e[ePos][0], e[ePos][1]);
            }
            for(auto& qq : qrs.second) {
                res[qq[2]] = getParent(gr, qq[0]) == getParent(gr, qq[1]);
            }
        }


        return res;
    }
};