题目地址：

https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/

给定一个$n$个顶点的无向带权图，要求应答若干次询问，每次询问问从点$p$到点$q$是否存在一条每条边都小于给定权值$x$的路径。可以离线应答。

思路是Kruskal算法。这里由于可以离线应答，所以可以先将所有询问按照$x$来从小到大排序，然后遍历询问，对每个询问$(p,q,r)$，模仿Kruskal算法的思路，先将权小于$r$的边建出来，并且用并查集把连通的点连成一个集合，应答询问的时候只需要看一下$p$与$q$是否连通即可。代码如下：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Solution {class UnionFind {int[] p;public UnionFind(int size) {p = new int[size];for (int i = 0; i < size; i++) {p[i] = i;}}public int find(int x) {if (p[x] != x) {p[x] = find(p[x]);}return p[x];}public void union(int x, int y) {int px = find(x), py = find(y);if (px != py) {p[px] = py;}}}public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {List<Integer> id = new ArrayList<>();for (int i = 0; i < queries.length; i++) {id.add(i);}id.sort((x, y) -> Integer.compare(queries[x][2], queries[y][2]));UnionFind uf = new UnionFind(n);Arrays.sort(edgeList, (e1, e2) -> Integer.compare(e1[2], e2[2]));boolean[] res = new boolean[queries.length];for (int i = 0, j = 0; i < id.size(); i++) {int idx = id.get(i);int x = queries[idx][0], y = queries[idx][1], len = queries[idx][2];while (j < edgeList.length && edgeList[j][2] < len) {// 把边权小于len的边先连起来uf.union(edgeList[j][0], edgeList[j][1]);j++;}res[idx] = uf.find(x) == uf.find(y);}return res;}
}

时间复杂度 O ( m log ⁡ m + q log ⁡ q + ( m + q ) log ⁡ ∗ n ) O(m\log m+q\log q+(m+q)\log^*n) O(mlogm+qlogq+(m+q)log∗n)，空间$O(m+q)$。

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