資料結構
網路
關係資料庫管理系統 (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
