leetcode-1697-检查边长度限制的路径是否存在

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 超过一条边 。

给你一个查询数组queries ，其中 queries[j] = [p_j, q_j, limit_j] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。

请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。

示例 1：

输入:n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
输出::[false,true]
解释:上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。
对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。
对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。

示例 2：

输入:n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
输出:[true,false]
解释:上图为给定数据。

提示：

• 2 <= n <= 105
• 1 <= edgeList.length, queries.length <= 105
• edgeList[i].length == 3
• queries[j].length == 3
• 0 <= ui, vi, pj, qj <= n - 1
• ui != vi
• pj != qj
• 1 <= dis_i, limit_j <= 10^9
• 两个点之间可能有 多条 边。

分析：

本题本质上其实是判断两点是否联通，只是路径上的边长度有所限制。因此可以用并查集，将在满足条件上联通的点合并，如果最后两点在同一个集合内，则说明路径存在。

class Solution {
public:vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {vector<bool> results;bool result;for(int i = 0; i < queries.size(); i++){vector<int> S = vector<int>(n,-1);//初始化并查集for(int j = 0; j < edgeList.size(); j++){//将符合条件的边上的点进行合并if(edgeList[j][2] < queries[i][2]){int root1 = Find(S,edgeList[j][0]);int root2 = Find(S,edgeList[j][1]);if(root1 != root2 || (root1 == -1 && root2 == -1))Union(S,root1,root2);}}if(Find(S,queries[i][0]) == Find(S,queries[i][1]))result = true;elseresult = false;results.push_back(result);}return results;}//并查集相关操作void initial(vector<int>& S){//并查集初始化for(auto i : S)i = -1;}void Union(vector<int>& S, int root1, int root2){//并查集合并//要求root1与root2不同S[root2] = root1;}int Find(vector<int>& S, int x){//查找包含元素x的树的根while (S[x] >= 0)x = S[x];return x;}
};

但是这种做法只能做到**12 / 23** 个通过测试用例，说明时间复杂度太差。

想要节省更多的时间，就得好好思考一下。

我们可以发现，在以更短的边为约束条件下构成的连通图，一定可以用于更长的边为约束条件的情况。因此我们可以按边的大小从小到大来对queries进行查询。

同样的道理，对于edgeList我们也能按顺序从小到大来排列，这样能将更小的边先加入连通图，而且能做到不回溯，节省非常多的时间。由此我们能够得到下列代码：

vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {//排序sort(edgeList.begin(), edgeList.end(), [](vector<int>& a,vector<int>& b) {return a[2] < b[2];});sort(queries.begin(), queries.end(), [](vector<int>& a, vector<int>& b) {return a[2] < b[2];});vector<bool> results;vector<int> S = vector<int>(n, -1);//初始化并查集bool result;int j = 0;//指向edgeList的当前序号for (int i = 0; i < queries.size(); i++) {while (j < edgeList.size() && edgeList[j][2] < queries[i][2]) {////将符合条件的边上的点进行合并if (edgeList[j][2] < queries[i][2]) {int root1 = Find(S, edgeList[j][0]);int root2 = Find(S, edgeList[j][1]);if (root1 != root2)Union(S, root1, root2);}j++;//指向下一位置}if (Find(S, queries[i][0]) == Find(S, queries[i][1]))result = true;elseresult = false;results.push_back(result);}return results;
}

但这时居然出错了，仔细研究后发现，原来是queries交换顺序后，使得结果的results也交换了顺序。

那么我们可以不交换queries的顺序，而是交换它的下标的顺序。

vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {//排序sort(edgeList.begin(), edgeList.end(), [](vector<int>& a,vector<int>& b) {return a[2] < b[2];});//由于queries需要按原来的顺序输出结果，因此不能对queries排序，可对其数组下标进行排序vector<int> index(queries.size());iota(index.begin(), index.end(), 0);//需要#includesort(index.begin(), index.end(), [&](int i1, int i2) {return queries[i1][2] < queries[i2][2];});vector<bool> results(queries.size());vector<int> S = vector<int>(n, -1);//初始化并查集bool result;int j = 0;//指向edgeList的当前序号for (auto i : index) {while (j < edgeList.size() && edgeList[j][2] < queries[i][2]) {////将符合条件的边上的点进行合并if (edgeList[j][2] < queries[i][2]) {int root1 = Find(S, edgeList[j][0]);int root2 = Find(S, edgeList[j][1]);if (root1 != root2)Union(S, root1, root2);}j++;//指向下一位置}if (Find(S, queries[i][0]) == Find(S, queries[i][1]))result = true;elseresult = false;results[i] = result;}return results;
}

修改后过了19/23个测试用例，居然还是超时了，很纳闷。

对着标准答案仔细研究许久后发现，并查集的Find函数和我写的不同。

我的写法：

int Find(vector<int>& S, int x){//查找包含元素x的树的根while (S[x] >= 0)x = S[x];return x;
}

答案写法：

int Find(vector<int>& S, int x){//查找包含元素x的树的根if(S[x] < 0){return x;}return S[x] = Find(S,S[x]);
}

可以看到，二者之间最大的区别就是答案中递归调用了Find函数。这个做法成为并查集的路径压缩，可以有效地减小并查集的深度。

最终代码

/*执行用时：
476 ms, 在所有 C++ 提交中击败了83.89%的用户
内存消耗：
107.8 MB, 在所有 C++ 提交中击败了68.46%的用户
通过测试用例：23 / 23*/
class Solution {
public:vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {//排序sort(edgeList.begin(), edgeList.end(), [](vector<int>& a,vector<int>& b) {return a[2] < b[2];});//由于queries需要按原来的顺序输出结果，因此不能对queries排序，可对其数组下标进行排序vector<int> index(queries.size());iota(index.begin(), index.end(), 0);//需要#includesort(index.begin(), index.end(), [&](int i1, int i2) {return queries[i1][2] < queries[i2][2];});vector<bool> results(queries.size());vector<int> S = vector<int>(n,-1);//初始化并查集bool result;int j = 0;//指向edgeList的当前序号for (auto i : index) {while (j < edgeList.size() && edgeList[j][2] < queries[i][2]) {////将符合条件的边上的点进行合并if (edgeList[j][2] < queries[i][2]) {int root1 = Find(S, edgeList[j][0]);int root2 = Find(S, edgeList[j][1]);if (root1 != root2)Union(S, root1, root2);}j++;//指向下一位置}if (Find(S, queries[i][0]) == Find(S, queries[i][1]))result = true;elseresult = false;results[i] = result;}return results;}//并查集相关操作void initial(vector<int>& S){//并查集初始化for(auto i : S)i = -1;}void Union(vector<int>& S, int root1, int root2){//并查集合并//要求root1与root2不同S[root2] = root1;}int Find(vector<int>& S, int x){//查找包含元素x的树的根if(S[x] < 0){return x;}//****************************************return S[x] = Find(S,S[x]);//这个地方非常重要}
};

通过今天的学习，对并查集的了解增进不少，也许感觉到难时才是在真正进步吧。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！