用 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，第二个为假，因为我们不能使用小于 3 的成本从 2 到 3，最后一个为真，因为我们可以使用路径 1 -> 3 -> 从 1 到 2 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() 。这将获取父级、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 和值 ch 的对 (i, ch) 列表
根据限制参数对查询进行排序
ind := 0
对于查询中的每个索引 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]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
