Python中检查边长限制路径存在性的程序

假设我们有一张使用一个edgeList的n个节点的无向加权图，其中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。第二个是错误的，因为我们不能从2到3使用小于3的距离，最后一个是正确的，因为我们可以沿着路径1->3->2，成本为14，小于15，从1到2。

为了解决这个问题，我们将按照以下步骤进行−

• 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]
  • parent[a]：= b
• 否则，当rank[a] >rank[b]时，
  • parent[b]：= a
• 否则，
  • parent[b]：= a

  • rank[a]：= rank[a]+1

• 从main方法执行以下操作−

• 基于weight参数对edgeList进行排序

• res：具有查询数量并填充为0的数组

• query：每个索引i和值ch从查询的一对（i，ch）的列表

• 基于limit参数对查询进行排序

• ind：= 0

• 对于查询中的每个索引i三元组（a，b，w），完成以下操作

  • 当ind < edgeList的大小且edgeList[ind，2]
    • 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]