本文主要是介绍1697. 检查边长度限制的路径是否存在,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Problem: 1697. 检查边长度限制的路径是否存在
文章目录
- 思路
- 解题方法
- 复杂度
- Code
思路
这是一个关于边长度限制路径存在性的问题。给定一个无向图,每条边都有一个长度。同时给定一些查询,每个查询包含两个节点和一个长度限制。需要判断是否存在一条路径连接这两个节点,并且路径上的边的长度都不超过限制。
可以使用并查集来解决这个问题。首先对边按照长度进行排序,然后对查询按照限制长度进行排序。然后使用并查集来判断两个节点是否在同一个连通分量中。遍历查询,对于每个查询,将小于等于限制长度的边添加到并查集中,然后判断两个节点是否在同一个连通分量中。
解题方法
创建一个大小为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 ( E l o g E + M l o g M ) O(ElogE + MlogM) O(ElogE+MlogM),其中E为边的数量,M为查询的数量。并查集的时间复杂度为 O ( l o g N ) O(logN) O(logN),其中N为节点的数量
空间复杂度:
O ( N ) O(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. 检查边长度限制的路径是否存在的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!