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

本文主要是介绍1697. 检查边长度限制的路径是否存在，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 1697. 检查边长度限制的路径是否存在

思路

这是一个关于边长度限制路径存在性的问题。给定一个无向图，每条边都有一个长度。同时给定一些查询，每个查询包含两个节点和一个长度限制。需要判断是否存在一条路径连接这两个节点，并且路径上的边的长度都不超过限制。

可以使用并查集来解决这个问题。首先对边按照长度进行排序，然后对查询按照限制长度进行排序。然后使用并查集来判断两个节点是否在同一个连通分量中。遍历查询，对于每个查询，将小于等于限制长度的边添加到并查集中，然后判断两个节点是否在同一个连通分量中。

解题方法

创建一个大小为n的数组father，用于存储每个节点的父节点。
创建一个大小为m的二维数组questions，用于存储查询的信息。其中questions[i][0]表示查询的起始节点，questions[i][1]表示查询的终止节点，questions[i][2]表示查询的限制长度，questions[i][3]表示查询的索引。
对边的列表edgeList按照边的长度进行排序。
对查询的列表queries按照限制长度进行排序。
使用并查集的find和union操作，遍历查询列表，对于每个查询，将小于等于限制长度的边添加到并查集中，然后判断起始节点和终止节点是否在同一个连通分量中。
将判断结果存储到一个大小为m的布尔数组ans中，ans[i]表示第i个查询的结果。
返回ans作为查询结果。

复杂度

时间复杂度:

排序边和查询的时间复杂度为$O(ElogE+MlogM)$，其中E为边的数量，M为查询的数量。并查集的时间复杂度为$O(logN)$，其中N为节点的数量

空间复杂度:

$O(N)$，用于存储并查集的father数组。

Code

class Solution {public int MAXN = 100001;public int[][] questions = new int[MAXN][4];public int[] father = new int[MAXN];public void build(int n) {for (int i = 0; i < n; i++) {father[i] = i;}}public int find(int i) {if (i != father[i]) {father[i] = find(father[i]);}return father[i];}public boolean isSameSet(int x, int y) {return find(x) == find(y);}public void union(int x, int y) {father[find(x)] = find(y);}public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {Arrays.sort(edgeList, (a, b) -> (a[2] - b[2]));int k = edgeList.length;int m = queries.length;for (int i = 0; i < m; i++) {questions[i][0] = queries[i][0];questions[i][1] = queries[i][1];questions[i][2] = queries[i][2];questions[i][3] = i;}Arrays.sort(questions, 0, m, (a, b) -> a[2] - b[2]);build(n);boolean[] ans = new boolean[m];for (int i = 0, j = 0; i < m; i++) {for (; j < k && edgeList[j][2] < questions[i][2]; j++) {union(edgeList[j][0], edgeList[j][1]);}ans[questions[i][3]] = isSameSet(questions[i][0], questions[i][1]);}return ans;}
}

这篇关于1697. 检查边长度限制的路径是否存在的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---