Deep and Step by Step Approach and Solution
Intuition\n Describe your first thoughts on how to solve this problem. \nAfter reading the problem, the first approach that came to my mind was to try to find a
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nAfter reading the problem, the first approach that came to my mind was to try to find an answer for each query using **Dijkstra**\'s algorithm. However, after analyzing the constraints, I realized that it would lead to a TLE (Time Limit Exceeded). As this approach takes O(Q*Nlog(E)) time.\n\nSince the problem requires us to check if a path exists between two nodes, I thought it could be solved using the **Disjoint Set Union (DSU)** data structure, as it helps to find the parent in nearly constant time.\n\n\n---\n\n\n\n# Approach\n1. Create a DisjointSet class to represent the graph, which will store the parent node for each node in the graph. Initially, each node is its own parent.\n2. Add a findParent method to the DisjointSet class, which finds the parent of a given node. If the parent of a node is itself, return the node, otherwise recursively call findParent on the parent of the node.\n3. Add a unionByRank method to the DisjointSet class, which takes two nodes and unions them together. The method finds the parent of each node, and if they are not the same, it merges the two sets by attaching the one with the smaller rank to the one with the larger rank.\n4. Add an isParentEqual method to the DisjointSet class, which checks if the parent of two nodes is the same. This method uses findParent to get the parent of each node and then checks if they are equal.\n5. Sort the edges by distance in non-decreasing order.\n6. Sort the queries by limit in non-decreasing order.\n7. For each query, loop through the edges until the distance is greater than the limit of the current query. For each edge, call the unionByRank method to merge the nodes together.\n8. After all edges less than the current query\'s limit have been processed, check if the parent of the source and destination nodes in the query are the same using the isParentEqual method. If they are, set the answer for the query to true, otherwise set it to false.\n9. Return the array of answers.\n\n\n---\n\n\n\n# Complexity\n- **Time complexity**:\n\n1. Sorting the edges takes O(ElogE) time.\n2. Sorting the queries takes O(QlogQ) time.\n3. For each query, we iterate through the edges up to limit distance. Therefore, for all queries, we iterate through all the edges at most once. So, iterating through all the edges takes O(E) time.\n4. Union-find operations take nearly O(1) time.\n5. Therefore, the total time complexity of the solution is O(ElogE + QlogQ + (O+E)).\n\n- **Space complexity**:\n\n1. We use a disjoint-set data structure to keep track of the connected components of the graph. The space required for this data structure is O(N).\n2.If we neglect space required to store answer, the total space complexity of the solution is O(N).\n\n\n---\n\n\n\n# Code\n```\nclass DisjointSet {\nprivate:\n    vector<int> parent, rank;\n\npublic:\n    DisjointSet(int n) {\n        parent.resize(n+1, 0);\n        rank.resize(n+1, 0);\n\n        for(int i=0; i<n+1; i++) {\n            parent[i] = i;\n        }\n    }\n\n    int findParent(int node) {\n        if(node == parent[node])\n            return node;\n        \n        return parent[node] = findParent(parent[node]);\n    }\n\n    void unionByRank(int u, int v) {\n        int upU = findParent(u);\n        int upV = findParent(v);\n\n        if(upU == upV)\n            return;\n        \n        if(rank[upU] < rank[upV]) {\n            parent[upU] = upV;\n        }\n        else {\n            parent[upV] = upU;\n            rank[upU]++;\n        }\n    }\n\n    bool isParentEqual(int u, int v) {\n        return (findParent(u) == findParent(v));\n    }\n};\n\nclass Solution {\n    bool static compare(const vector<int> &a, const vector<int> &b) {\n        return (a[2] < b[2]);\n    }\n\npublic:\n    vector<bool> distanceLimitedPathsExist(int nodes, vector<vector<int>>& edges, vector<vector<int>>& queries) {\n        int n = queries.size();\n\n        vector<bool> ans(n, false);\n        \n        for(int i=0; i<n; i++) {\n            queries[i].push_back(i);\n        }\n\n        sort(edges.begin(), edges.end(), compare);\n        sort(queries.begin(), queries.end(), compare);\n\n        DisjointSet ds(nodes);\n        int i=0;\n\n        for(auto &query : queries) {\n            int u = query[0];\n            int v = query[1];\n            int limit = query[2];\n            int qId = query[3];\n\n            for(; (i < edges.size()) && (edges[i][2] < limit); i++) {\n                ds.unionByRank(edges[i][0], edges[i][1]);\n            }\n            ans[qId] = ds.isParentEqual(u, v);\n        }\n\n        return ans;\n    }\n};\n```\n\n\n---\n\n**Happy Coding...**\n\n
['Union Find', 'Graph', 'Sorting', 'C++']