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

题目描述

这是 LeetCode 上的 1697. 检查边长度限制的路径是否存在 ,难度为 困难

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

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

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

示例 1:

1
2
3
4
5
6
7
输入:n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]

输出:[false,true]

解释:上图为给定的输入数据。注意到 01 之间有两条重边,分别为 216
对于第一个查询,01 之间没有小于 2 的边,所以我们返回 false
对于第二个查询,有一条路径(0 -> 1 -> 2)两条边都小于 5 ,所以这个查询我们返回 true

示例 2:

1
2
3
4
5
输入: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 <= 10^5$
  • $1 <= edgeList.length, queries.length <= 10^5$
  • $edgeList[i].length == 3$
  • $queries[j].length == 3$
  • $0 <= u_i, v_i, p_j, q_j <= n - 1$
  • $u_i != v_i$
  • $p_j != q_j$
  • $1 <= dis_i, limit_j <= 10^9$
  • 两个点之间可能有多条边。

排序 + 并查集 + 双指针

为了方便,我们将点数记为 n,边数记为 m,询问数量记为 k,将 edgeList 简化为 es,将 queries 简化为 qs

对于点边数量都在 $10^5$,同时询问次数也在 $10^5$ 的问题,不可能对于每个询问执行最短路算法,尤其还需考虑边权限制。

对于一个询问 $(a, b, limit)$ 而言,等价于问我们使用所有边权小于 limit 的边,能否使得 ab 两点联通。

关于回答连通性问题,容易想到并查集。同时我们可以通过「调整回答询问的顺序」来降低复杂度(避免重复重置并查集和添加某些边),即转换为离线问题来处理。

何为离线问题?预先知道所有询问,能够通过调整回答询问的顺序,来降低算法复杂度。同时不同询问相互独立,不会因为调整询问顺序,对每个询问的结果造成影响。例如莫队算法。

具体的,我们可以对边集 es 和所有询问 qs 分别按照「边权」以及「限制」排升序。为了排序后,仍能知道当前询问的原编号,我们要将所有的 qs[i] 转换为四元组。

随后从前往后处理每个询问 qs[i] = (a, b, t, idx),同时使用变量 j 来记录当前处理到的边。在查询 ab 是否连通前,先将边集 es 中所有所有边权小于 t 的边应用到并查集上,从而实现每次 ans[idx] = query(a, b) 查询到的是原图中所有边权小于限制值 t 的子图。

Java 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
static int N = 100010;
static int[] p = new int[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void union(int a, int b) {
p[find(a)] = p[find(b)];
}
boolean query(int a, int b) {
return find(a) == find(b);
}
public boolean[] distanceLimitedPathsExist(int n, int[][] es, int[][] _qs) {
for (int i = 0; i < n; i++) p[i] = i;
int m = es.length, k = _qs.length;
int[][] qs = new int[k][4];
for (int i = 0; i < k; i++) qs[i] = new int[]{_qs[i][0], _qs[i][1], _qs[i][2], i};
Arrays.sort(qs, (a,b)->a[2]-b[2]);
Arrays.sort(es, (a,b)->a[2]-b[2]);
boolean[] ans = new boolean[k];
for (int i = 0, j = 0; i < k; i++) {
int a = qs[i][0], b = qs[i][1], t = qs[i][2], idx = qs[i][3];
while (j < m && es[j][2] < t) {
union(es[j][0], es[j][1]);
j++;
}
ans[idx] = query(a, b);
}
return ans;
}
}

C++ 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
int p[100010];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void unite(int a, int b) {
p[find(a)] = find(b);
}
bool query(int a, int b) {
return find(a) == find(b);
}
vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& es, vector<vector<int>>& qs) {
for (int i = 0; i < n; i++) p[i] = i;
int m = es.size(), k = qs.size();
vector<vector<int>> qss(k, vector<int>(4, 0));
for (int i = 0; i < k; i++) qss[i] = {qs[i][0], qs[i][1], qs[i][2], i};
sort(qss.begin(), qss.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
sort(es.begin(), es.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
vector<bool> ans(k, false);
for (int i = 0, j = 0; i < k; i++) {
int a = qss[i][0], b = qss[i][1], t = qss[i][2], idx = qss[i][3];
while (j < m && es[j][2] < t) {
unite(es[j][0], es[j][1]);
j++;
}
ans[idx] = query(a, b);
}
return ans;
}
};

Python 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def distanceLimitedPathsExist(self, n: int, es: List[List[int]], _qs: List[List[int]]) -> List[bool]:
p = [i for i in range(n)]
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
p[find(a)] = p[find(b)]
def query(a, b):
return find(a) == find(b)
m, k = len(es), len(_qs)
qs = [(a, b, c, i) for i, (a, b, c) in enumerate(_qs)]
es.sort(key=lambda x: x[2])
qs.sort(key=lambda x: x[2])
j = 0
ans = [False] * k
for i in range(k):
a, b, t, idx = qs[i]
while j < m and es[j][2] < t:
union(es[j][0], es[j][1])
j += 1
ans[idx] = query(a, b)
return ans

TypeScript 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function distanceLimitedPathsExist(n: number, es: number[][], _qs: number[][]): boolean[] {
const p = new Array<number>(n).fill(0)
for (let i = 0; i < n; i++) p[i] = i;
function find(x: number): number {
if (p[x] != x) p[x] = find(p[x])
return p[x]
}
function union(a: number, b: number): void {
p[find(a)] = p[find(b)]
}
function query(a: number, b: number): boolean {
return find(a) == find(b)
}
const m = es.length, k = _qs.length
const qs = []
for (let i = 0; i < k; i++) qs.push([_qs[i][0], _qs[i][1], _qs[i][2], i])
qs.sort((a, b)=>a[2]-b[2])
es.sort((a, b)=>a[2]-b[2])
const ans = new Array<boolean>(k).fill(false)
for (let i = 0, j = 0; i < k; i++) {
const a = qs[i][0], b = qs[i][1], t = qs[i][2], idx = qs[i][3]
while (j < m && es[j][2] < t) {
union(es[j][0], es[j][1])
j++
}
ans[idx] = query(a, b)
}
return ans
}

  • 时间复杂度:初始化并查集的复杂度为 $O(n)$;对所有边进行排序复杂度为 $O(m\log{m})$;对所有询问进行排序复杂度为 $O(k\log{k})$;统计答案时使用双指针的方式将所有边运用到并查集上,整体复杂度为 $O(k + m)$。整体复杂度为 $O(n + m\log{m} + k\log{k})$
  • 空间复杂度:$O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1697 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。