[C++] DSU + Two Pointers
Observation\n\nThe key here is to notice that the queries are offline which means that we can reorganize them however we want.\n\nNow to answer the question, wh
**Observation**\n\nThe key here is to notice that the queries are offline which means that we can reorganize them however we want.\n\nNow to answer the question, whether there is a path between any two nodes where the maximum edge length or weight is less than `limit`, we can join all the edges whose weight is less than `limit` and if we are still not able to reach one node from the other it essentially means that there is no path between them where edge weight is less than `limit`.\n\nWhich is the best data structure that can help us join edges as we want and answer whether in that structure, node `a` and node `b` are connected ? \nThat\'s right! **DSU**.\n\nLet\'s try and use these facts to solve the question.\n\n**Solution**\n\nFirst we need to sort the input `queries` and `edgeList` by edge length or `weight`.\n\nWe can now simply use a two pointer approach to `Union` all the nodes whose edges have `weight` less than `query[i]`.\n\nTo know if there is a path between them all we need is to know whether their parents (in DSU) are same.\n\n```c++\n// Standard Disjoint-set data structure implementation.\nstatic class DSU {\n    vector<int> Parent, Rank;\n    public:\n    DSU(int n) {\n        Parent.resize(n);\n        Rank.resize(n, 0);\n        for (int i = 0; i < n; i++) Parent[i] = i;\n    }\n    int Find(int x) {\n        return Parent[x] = Parent[x] == x ? x : Find(Parent[x]);\n    }\n    bool Union(int x, int y) {\n        int xset = Find(x), yset = Find(y);\n        if (xset != yset) {\n            Rank[xset] < Rank[yset] ? Parent[xset] = yset : Parent[yset] = xset;\n            Rank[xset] += Rank[xset] == Rank[yset];\n            return true;\n        }\n        return false;\n    }\n};\nclass Solution {\npublic:\n    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries)\n    {\n        DSU dsu(n);\n\t\t\n\t\t//Add query indices to help with organizing/ordering results.\n        for(int i=0;i<queries.size();i++)\n            queries[i].push_back(i);\n\t\t\n\t\t//Sort inputs\n        sort(queries.begin(), queries.end(), [](auto &l, auto &r) { return l[2] < r[2]; });\n        sort(edgeList.begin(), edgeList.end(), [](auto &l, auto &r) { return l.back() < r.back(); });\n\t\t\n        int i=0;\n        vector<bool> result(queries.size());\n        for (vector<int> &q:queries) \n        {\n\t\t\t// Two pointer approach. Join the edges till their weight is less than the current query.\n            while (i<edgeList.size()&&edgeList[i][2]<q[2]) \n                dsu.Union(edgeList[i][0],edgeList[i++][1]);\n\t\t\t\n\t\t\t//If parents are same we know that their is a path.\n            result[q.back()]=dsu.Find(q[0]) == dsu.Find(q[1]);\n        }\n        return result;\n    }\n};\n```\n**Complexity**\nTime: `O(ElogE + QlogQ)`. Where `E` is the number of edges in `edgeList` and `Q` is the number of `queries`. This comes from sorting both inputs.\nSpace: `O(n)`. Where `n` is the number of nodes.
[]