检查边长度限制的路径是否存在【LC1679】
给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 超过一条边 。
给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。
请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。
An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.
Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .
Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.
同门阳了 我指希望不要太难受 这周把这类并查集搞定
BFS【超时】
- 思路：将输入的 edgeList转换成邻接表 adList，维护一个小顶堆 pq 可以暴力计算出查询数组queries中各个起点到各个终点边长度最短的路径，从而判断是否存在办长度限制的路径
。pq 中的元素为节点编号以及起点到该节点的路径长度，并以路径长度为比较元素。每次取出未访问过的节点中的路径最短的节点，并访问其邻接点，若路径长度仍小于等于 queries[2]且未访问过，可将其放入 pq，直至 pq 为空或 边大于queries[2]。
- 实现
class Solution { public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) { boolean[] res = new boolean[queries.length]; // 构建邻接表 List<int[]>[] adList = new List[n]; for (int i = 0; i < n; i++){ adList[i] = new ArrayList<int[]>(); } for (int[] edge : edgeList){ int u = edge[0], v = edge[1], dis = edge[2]; adList[u].add(new int[]{v, dis}); adList[v].add(new int[]{u, dis}); } for (int i = 0; i < queries.length; i++){ int start = queries[i][0], end = queries[i][1], limit = queries[i][2]; PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]); pq.offer(new int[]{0, start}); Set<Integer> visited = new HashSet<>(); // 寻找路径 while(!pq.isEmpty() && pq.peek()[0] < limit){ int[] poll = pq.poll(); int dis = poll[0], u = poll[1]; if (!visited.add(u)){ continue; } if (u == end){ res[i] = true; break; } // 加入下一个可以访问的节点 for (int[] next : adList[u]){ int v = next[0], disNext = next[1]; if (!visited.contains(v)){ pq.offer(new int[]{disNext, v}); } } } } return res; } }
。复杂度
- 时间复杂度：O(E×logV×m)，V 为节点数，即 n ，E为输入edgeList 的长度，m 为queries的长度。邻接表 adList的时间复杂度为O(E)，搜索路径的时间复杂度为O(E×logV)。
- 空间复杂度：O(V+E)，邻接表 adList 的空间复杂度为O(E)，pq 的空间复杂度为O(E)，visited 的空间复杂度为 O ( V ) ，总的空间复杂度为 O(V+E)。
并查集
- 离线查询：对于一道题目会给出若干询问，而这些询问是全部提前给出的，也就是说，你不必按照询问的顺序依次对它们进行处理，而是可以按照某种顺序（例如全序、偏序（拓扑序）、树的 DFS 序等）或者把所有询问看成一个整体（例如整体二分、莫队算法等）进行处理。
- 思路：
。使用并查集维护图的连通性，对于queries[i],我们可以将edgeList中所有长度小于limit的边加入到并查集中，然后使用并查集查询u和v是否属于同一个集合。如果 u和 v属于同一个集合，则说明存在从 u到 v的路径，且这条路径上的每一条边的长度都严格小于 limit，查询返回true，否则查询返回false。
。因此可以将queries按照limit从小到大进行排序，并将edgeList按照距离dis从小到大进行排序，使用指针k定位上一次查询中不满足limit要求的长度最小的边，以便于使用离线查询的思维处理queries中的询问，降低时间复杂度
- 实现
1.排序
2.依次遍历 queries：如果 k 指向的边的长度小于对应查询的 limit，则将该边加入并查集中，然后将 k加 1，直到 k指向的边不满足要求；最后根据并查集查询对应的u和v是否属于同一集合来保存查询的结果。
class Solution { private int[] father; public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) { // 记录初始下标 Integer[] index = new Integer[queries.length]; for (int i = 0; i < queries.length; i++){ index[i] = i; } // 排序 Arrays.sort(edgeList, (a, b) -> a[2] - b[2]); Arrays.sort(index, (a, b) -> queries[a][2] - queries[b][2]); // 并查集初始化 father = new int[n]; for (int i = 0; i < n; i++){ father[i] = i; } boolean[] res = new boolean[queries.length]; int k = 0; for (int i : index){ while (k < edgeList.length && edgeList[k][2] < queries[i][2]){ join(edgeList[k][0],edgeList[k][1]); k++; } res[i] = find(queries[i][0]) == find(queries[i][1]); } return res; } private int find(int u){ if (u == father[u]){ return u; } father[u] = find(father[u]); return father[u]; } private void join (int u, int v){ u = find(u); v = find(v); if (u == v) return; father[v] = u; } }
。复杂度
- 时间复杂度：O(ElogE+mlogm+(E+m)logn+n)，n 为节点数，E 为输入edgeList 的长度，m 为queries的长度。对edgeList和queries 排序时间复杂度分别为 O(ElogE)和 O(mlogm)，并查集初始化的时间复杂度为O(n)，并查集查询和合并的时间复杂度为O((E+m)logn)。
- 空间复杂度：O(logE+m+n)，保存并查集的空间复杂度为O(n)，保存下标的空间复杂度为O(m)，对edgeList排序的空间复杂度为O(logE)，对queries排序的空间复杂度可以忽略
