数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学Python程序：检查是否存在边长受限路径
假设我们有一个包含n个节点的无向加权图，使用一个edgeList表示，其中edgeList[i]包含三个参数(u, v, w)，表示从u到v有一条距离为w的路径。我们还有一个查询数组，其中query[i]包含(p, q, lim)。此查询试图询问是否存在一条路径(直接或通过其他节点)从p到q，其距离小于lim。我们必须返回一个数组，其中包含每个查询的True/False结果。
因此，如果输入如下所示：
则输出将为[True, False, True]。因为要从1到4，我们可以沿着路径1 -> 3 -> 4走，成本为11；第二个是false，因为我们无法使用小于3的成本从2到3；最后一个是true，因为我们可以使用路径1 -> 3 -> 2，成本为14，小于15。
为了解决这个问题，我们将遵循以下步骤：
parent := 从0到n的一个列表
rank := 大小为n+1的列表，并填充0
定义一个函数find()。它将接收parent和x。
如果parent[x]与x相同，则
返回x
parent[x] := find(parent, parent[x])
返回parent[x]
定义一个函数union()。它将接收parent, a, b。
a := find(parent, a)
b := find(parent, b)
如果a与b相同，则
返回
如果rank[a] < rank[b]，则
parent[a] := b
否则，如果rank[a] > rank[b]，则
parent[b] := a
否则，
parent[b] := a
rank[a] := rank[a] + 1
在主方法中执行以下操作：
根据权重参数对edgeList进行排序
res := 一个包含查询数量的数组，并填充0
queries := 每个索引i和来自queries的值ch的配对列表
根据限制参数对queries进行排序
ind := 0
对于queries中每个索引i三元组(a, b, w)，执行以下操作：
当ind < edgeList的大小且edgeList[ind, 2] < w时，执行以下操作：
union(parent, edgeList[ind, 0])
ind := ind + 1
res[i] := find(parent, a)与find(parent, b)相同
返回res
示例
让我们看下面的实现，以便更好地理解
def solve(n, edgeList, queries):
parent = [i for i in range(n+1)]
rank = [0 for i in range(n+1)]
def find(parent, x):
if parent[x] == x:
return x
parent[x] = find(parent, parent[x])
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
if a == b:
return
if rank[a] < rank[b]:
parent[a] = b
elif rank[a] > rank[b]:
parent[b] = a
else:
parent[b] = a
rank[a] += 1
edgeList.sort(key = lambda x: x[2])
res = [0] * len(queries)
queries = [[i, ch] for i, ch in enumerate(queries)]
queries.sort(key = lambda x: x[1][2])
ind = 0
for i, (a, b, w) in queries:
while ind < len(edgeList) and edgeList[ind][2] < w:
union(parent, edgeList[ind][0], edgeList[ind][1])
ind += 1
res[i] = find(parent, a) == find(parent, b)
return res
n = 4
edgeList = [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3),]
queries = [(1,4,12),(2,3,3),(1,2,15)]
print(solve(n, edgeList, queries))输入
4, [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)],[(1,4,12),(2,3,3),(1,2,15)]
输出
[True, False, True]
浏览量：128
