Distance Limited Paths Exist using Disjoint Set Union in C++// Easy to Understand
Intuition\nTo solve the problem, we can use Kruskal\'s algorithm to find the minimum spanning tree of the given graph, and then use this tree to answer the quer
# Intuition\nTo solve the problem, we can use Kruskal\'s algorithm to find the minimum spanning tree of the given graph, and then use this tree to answer the queries.\n\nWe first sort the edges of the graph in non-decreasing order of their weights. We then pick the edges one by one, and add them to the tree if they do not create a cycle. To check if an edge creates a cycle, we can use a disjoint set data structure. We then process the queries one by one, and check if the two nodes of each query are connected in the minimum spanning tree and the distance between them is less than the given limit.\n\nIf the two nodes of a query are connected in the minimum spanning tree and the distance between them is less than the given limit, then we mark the answer for this query as true, otherwise we mark it as false. Finally, we return the array of answers for all the queries.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Sort the edgeList in non-descending order of their weights.\n2. For each query in queries, sort the edgeList up to the limit of the query.\n3. Use a modified version of Dijkstra\'s algorithm to find a path between the two nodes of each query.\n4. In the modified Dijkstra\'s algorithm, stop exploring the neighboring nodes once the weight of the edge between the current node and a neighboring node exceeds the limit of the query.\n5. If a path is found between the two nodes of a query, mark the query as true in the answer array. Otherwise, mark it as false.\n6. Return the answer array.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n- The TimeComplexity O((m+n) log m), where m is the number of edges in edgeList and n is the number of queries in queries. This is because the edges are sorted using quicksort, which has an average-case time complexity of O(m log m), and the queries are also sorted, which takes O(n log n) time. \n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n- The space complexity of the code is O(m+n), where m is the number of edges in edgeList and n is the number of queries in queries. \n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n\n...............................................................................................................\nPLEASE UPVOTE IF YOU FIND THAT IT HELPED YOU ...............................................................................................................\n\n# Code\n```\nclass DisjointSet{\n    public:\n    vector<int>size;\n    vector<int>head;\n    DisjointSet(int n){\n        size.resize(n,1);\n        head.resize(n);\n        for(int i=0;i<n;i++)head[i]=i;\n    }\n    \n    int findUpar(int node){\n        if(node==head[node])return node;\n\n       return head[node]=findUpar(head[node]);\n    }\n\n    void UnionBySize(int u,int v){\n        int jms=findUpar(u);\n        int rms=findUpar(v);\n        if(jms==rms)return ;\n        if(size[jms]<size[rms]){\n            head[jms]=rms;\n            size[rms]+=size[jms];\n        }\n        else{\n            head[rms]=jms;\n            size[jms]+=size[rms];\n        }\n       \n    }\n};\n\nclass Solution {\npublic:\n    static bool cmp(vector<int>&a,vector<int>&b){\n        return a[2]<b[2];\n    }\n    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {\n        DisjointSet ds(n);\n        \n        for(int i=0;i<queries.size();i++){\n            queries[i].push_back(i);\n        }\n        vector<bool>ans(queries.size(),false);\n        sort(queries.begin(),queries.end(),cmp);\n        sort(edgeList.begin(),edgeList.end(),cmp);\n        int j=0;\n        for(int i=0;i<queries.size();i++){\n            while(j<edgeList.size()&&edgeList[j][2]<queries[i][2]){\n                ds.UnionBySize(edgeList[j][0],edgeList[j][1]);\n                j++;\n            }\n            if(ds.findUpar(queries[i][0])==ds.findUpar(queries[i][1])){\n                ans[queries[i][3]]=true;\n            }\n        }\n        return ans;\n\n    }\n};\n\n\n\n```
['C++']