[C++] | SimpleDSU w/ DETAILED EXPLANATION & COMMENTED CODE | Easy To Understand
Intuition\n Describe your first thoughts on how to solve this problem. \n\n1) We can apply BFS or DFS to find answer from moving one node\nto anothoer node. Obv
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n```\n1) We can apply BFS or DFS to find answer from moving one node\nto anothoer node. Obviously, traversing it queries number of time may \nlead to TLE.\n2) Instead of that we can apply DSU (Disjoint set Union) and why DSU ?\n3) In question we have to tell for each query that whether we are \nable to reach from one node to anthor node in less than limit value\nwhen we are given edges with distance values.\n4) So, for every queries[limit] value, we will try to find path in\nedges array that less than this limit value, how many nodes are \nwe able to travel.\n```\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n```\n5) Finally we will see that if in less than this limit we are able \nto make a group of nodes we can travel. \n6) If in this group both queries node also present than we answer \nwill be true for this index elsewise false.\n7) Now, why first: We will sort the edges array \nas will as the queries array.\n8) See, we will creating groups of nodes with the help of DSU that\nless than this limit value we are able to reach this number of nodes.\nIf we will sort the queries array on the basis of limit value then for\nith query limit we already know that less than this limit value,\nwe already group nodes, so by moving in increasing order we don\'t\nneed to create group again. There is much probaility that for covering\ncurrent ith value limit, maybe two of the nodes ask in queries already\ncovered with much less value and if it that, we already cover them \nin a group. \n9) Sorting edges array on the basis of weight help us in \nmoving linear increasing order as per by the queries limit values.\n```\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n```\nTime Complexity: O(n + q + szlogsz + qlogq + (sz + q) + n),\nsz: size of edges, q: size of queries\n\nwhere 1) n: no of nodes (intially making each node as parent of itslef)\n      2) q: holding up the exact/original indices for each query\n      3) szlogsz: sorting the edges array\n      4) qlogq: sorting the queries array \n      5) (sz + q): worst case for each query limit value \n        there is only one edge array\n      6) n: recursive find function used to find parent\n```\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n```\nSpace Complexity: O(n + n + q) \n       1) defining parent array of size n\n       2) anthor n (recursive stack space used to find parent)\n       3) anthor q, to store answer\n```\n\n# Code\n```\nclass Solution {\npublic:\n// find function which is used to find parent of a node\n    int find(int node, vector<int>& parent)\n    {\n        // if node is parent of itself return here\n        if(node == parent[node])\n            return node;\n        \n        // else go on in finding actual parent\n        return parent[node] = find(parent[node], parent);\n    }\n    \n    // union funtion to merge parents of two nodes\n    void Union(int node0, int node1, vector<int>& parent)\n    {\n        int par0 = find(node0, parent); // find parent of node zero\n        int par1 = find(node1, parent); // find parent of node one\n        \n        // if values of parents of node zero and one are equal \n        // then we will return true from here\n        if(par0 == par1)\n            return;\n        \n        // make parent of one anothoer (parent[par1] = par0, also valid)\n        parent[par0] = par1;\n    }\n\n    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {\n        int q = queries.size(); // defining size of queries array\n        int sz = edges.size(); // defining size of edges array \n\n        // Intiliaze parent array, which will take care of parent of every node\n        vector<int> parent(n, 0); \n\n        // intially make parent of everyone itself\n        for(int i = 0; i < n; i++) parent[i] = i;\n\n        // sort edges on the basis of distance weight\n        sort(edges.begin(), edges.end(), [&](vector<int>& edge1, vector<int>& edge2){\n            return edge1[2] < edge2[2];\n        });\n\n        // keep track of original indices\n        for(int i = 0; i < q; i++) queries[i].push_back(i);\n        \n        // sort queries on the basis of weight\n        sort(queries.begin(), queries.end(), [&](vector<int>& query1,vector<int>& query2) {\n            \n            return query1[2] < query2[2];\n        });\n\n        // declare answer array of size q, intially everything false\n        vector<bool> ans(q, false);\n        int edgeMoment = 0; // pointer to move in edges array\n\n        // now, for each query we will calculate answer\n        for(int eachQuery = 0; eachQuery < q; eachQuery++) {\n            int currQueryWeight = queries[eachQuery][2]; // currentWeight in queries\n            \n            // move in edges till edge distane weight less than currQueryWeight \n            // and map parents\n            while(edgeMoment < sz && edges[edgeMoment][2] < currQueryWeight)\n            Union(edges[edgeMoment][0], edges[edgeMoment][1], parent), edgeMoment++;\n\n            // if for this currQueryWeight, queries nodes found in same group,\n            // put answer true\n            if(find(queries[eachQuery][0], parent) == \n            find(queries[eachQuery][1], parent))  {\n\n                ans[queries[eachQuery][3]] = true;\n            }\n        }\n        \n        // finally, return ans\n        return ans;\n    }\n};\n```
['Union Find', 'Graph', 'C++']