假设我们有一个无向加权图,其中 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使用路径 1 -> 3 -> 2 到 2,成本 14 小于 15。
让我们看看以下实现以更好地理解
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]