难度: Hard
Submission
运行时间: 284 ms
内存: 26.3 MB
class DistanceLimitedPathsExist:
def find(self, i, d):
if self.fa[i] == i or self.dists[i] >= d:
return i
return self.find(self.fa[i], d)
def union(self, u, v, d):
fu, fv = self.find(u, inf), self.find(v, inf)
if fu != fv:
if self.levels[fu] > self.levels[fv]:
self.fa[fv] = fu
self.dists[fv] = d
else:
self.fa[fu] = fv
self.dists[fu] = d
if self.levels[fu] == self.levels[fv]:
self.levels[fv] += 1
def __init__(self, n: int, edgeList: List[List[int]]):
self.dists = [inf] * n
self.levels = [0] * n
self.fa = list(range(n))
for u, v, d in sorted(edgeList, key=lambda e:e[2]):
self.union(u, v, d)
def query(self, p: int, q: int, limit: int) -> bool:
return self.find(p, limit) == self.find(q, limit)
# Your DistanceLimitedPathsExist object will be instantiated and called as such:
# obj = DistanceLimitedPathsExist(n, edgeList)
# param_1 = obj.query(p,q,limit)
Explain
这道题目使用了Union-Find数据结构来解决边长度限制的路径查询问题。Union-Find通常用于处理动态连通性问题。在这个问题中，我们对边按照长度进行排序，并逐步将它们加入到一个并查集中。每个操作都会更新节点的连接关系和边界限制。这使得我们可以对于每个查询有效地判断两个节点是否可以通过一条边长限制在指定值以下的路径相连。 具体来说，初始化时，对所有边按照长度升序排序，并逐一合并节点。节点合并时，会更新根节点之间的最大边界。查询时，我们检查两个节点是否可以通过小于限制的边连接起来。
时间复杂度: O(E log E + Eα(n) + Qα(n))
空间复杂度: O(n + E)
class DistanceLimitedPathsExist:
def find(self, i, d):
# 寻找节点i的根节点，并应用路径压缩，同时根据距离d更新根节点
if self.fa[i] == i or self.dists[i] >= d:
return i
return self.find(self.fa[i], d)
def union(self, u, v, d):
# 合并节点u和v，设置它们的根节点，并根据它们的等级更新树的高度
fu, fv = self.find(u, inf), self.find(v, inf)
if fu != fv:
if self.levels[fu] > self.levels[fv]:
self.fa[fv] = fu
self.dists[fv] = d
else:
self.fa[fu] = fv
self.dists[fu] = d
if self.levels[fu] == self.levels[fv]:
self.levels[fv] += 1
def __init__(self, n: int, edgeList: List[List[int]]):
# 初始化并查集和边界数组
self.dists = [inf] * n
self.levels = [0] * n
self.fa = list(range(n))
# 对边按距离排序并逐个合并
for u, v, d in sorted(edgeList, key=lambda e:e[2]):
self.union(u, v, d)
def query(self, p: int, q: int, limit: int) -> bool:
# 查询两个节点是否可以通过距离小于limit的路径连接
return self.find(p, limit) == self.find(q, limit)
Explore
在初始化并查集时，`dists`数组的每个元素被设置为无穷大（inf），这代表没有任何边连接到该节点。当执行`union`操作时，如果两个节点之间的边长度`d`小于已经存在的距离，我们会更新两个节点的根节点的`dists`值为新的边长`d`。这个更新只有在新的边长`d`小于已经记录的距离时才会发生。对于边的长度超过查询的限制情况，在查询函数中，我们会检查两个节点是否可以通过路径压缩和当前记录的最小距离来确定是否存在一条边长小于或等于查询限制的路径。如果所有连接边的长度都超过查询限制，则这些边不会影响查找操作的结果。
路径压缩是并查集优化技术的一部分，用于减少查找根节点的路径长度。在执行路径压缩时，我们同时更新节点到其根节点的距离。具体来说，当我们递归查找节点的根节点时，我们不仅将节点直接连接到根节点，而且我们还更新节点到根节点的距离。这是通过聚合沿途遇到的所有边的最大距离来实现的。等级信息（或树的高度）也在`union`操作中更新，如果两个树的高度相同并且它们被合并，则合并后的树的高度会增加1。
在并查集的`union`操作中，我们通常不直接维护两个节点之间最短路径的距离，而是维护可以连接两个节点的有效边的最大值。当我们按照边的长度排序并逐步添加到并查集中时，我们保证了任何时候记录的都是连接两个集合的最小可用边。因此，尽管`d`可能不是历史上两个节点之间的最短路径，但它是在给定时间点内将两个节点连接起来的有效的最小边。
查询操作中的`find`方法通过检查两个节点是否具有相同的根节点来确定它们是否连通。为了确保这种连通性是在指定的`limit`范围内，我们在查找根节点的过程中应用了路径压缩，并检查沿途的每个节点的`dists`值是否满足小于`limit`的条件。如果在到达根节点前`dists`值超过了`limit`，则这条路径不符合条件，两个节点被认为是不连通的。这确保了我们准确地返回了是否存在一条边长小于`limit`的路径连接这两个节点。