✅[C++] Disjoin Set Union
This question is so far one of the best problem of DSU. \n\nHow to identify DSU? \nWell, in questions where we are asked to reach one node from another, or wher
This question is so far one of the best problem of DSU. \n\n**How to identify DSU?** \nWell, in questions where we are asked to reach one node from another, or where we need to attach nodes or form components of similiar types, we go with DSU. In DSU questions, most of the time, we are not given any extra conditions on the path, like shortest, longest, etc. We just need to find if we could reach from one node to another. \n\n**What to do after identifying?**\nThe only two functions in DSU are `join(Node1, Node2)`, to join two nodes, and `find(Node)` to find the godfather of the component to which `Node` belongs.\nNow we can use `Rank` to optimize the join function and `path-compression` to optimize the find function. I\'ve use path-compression only. \n\n**How to approach this question?**\nIn this question, we are given queries and edges. Now, in questions where we have to use DSU, we dont actually need to form the graph, we just have to join two nodes whose parents are not same. \nIn this problem, if we sort the queries and edges array based limits, then we would be able to use the precomputed answer. \n**How?** After sorting both of the arrays based on limits, for each query, we can loop in the edges vector and for each pair of node whose dist < limit, we can join them together. Joining them signifies that for the given limit, there exists a path between those two nodes which has all the edges < curr_limit.\n\n\n```\nvector <int> parent(100005,-1);\nclass Solution {\npublic:\n    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {\n        for(int i = 0; i<=n; i++) parent[i] = i;\n        \n\t\t// Sorting the edges array based on dist of each pair of node. \n        sort(edges.begin(),edges.end(),[](vector<int>&a, vector<int>&b){\n            if(a[2]<b[2]) return true;\n            return false;\n        });\n\n\t\t// We will need the indices of query elements coz after sorting, the order will change. \n\t\t// So we push the index in the same element vector of query.\n        for(int i = 0; i<queries.size(); i++) queries[i].push_back(i);\n\t\t\t\n\t\t// Sorting queries based on limits. \n        sort(queries.begin(),queries.end(),[](vector<int>&a,vector<int>&b){\n            if(a[2]<b[2]) return true;\n            return false;\n        });\n        \n        vector <bool> ans(queries.size(),false);\n        int idx = 0;\n        for(int i = 0; i<queries.size(); i++){\n            // Here we loop on edges vector and join the two nodes having dist < curr_limit.\n\t\t\twhile(idx<edges.size() and edges[idx][2]<queries[i][2]){\n                join(edges[idx][0],edges[idx][1]);\n                idx++;\n            }\n\t\t\t// If the two nodes of current query has same godfather, we set this queries ans as true\n            if(find(parent[queries[i][0]]) == find(parent[queries[i][1]])) ans[queries[i][3]] = true;\n        }\n        return ans;\n    }\nprotected:\n    int find(int x){\n        if(parent[x]==x) return x;\n        return parent[x] = find(parent[x]);\n    }\n    void join(int a, int b){\n        a = find(a);\n        b = find(b);\n        \n        if(a!=b) parent[b] = a;\n    }\n};\n```
['Union Find', 'C', 'C++']