1697. Checking Existence of Edge Length Limited Paths
给你一个 edge-weighted undirected graph
query 很多起始结束点和上限权重
看他们之间有没有一条权重全部小于这个上限的路径
两点之间可以有多个边
Example 1:
https://assets.leetcode.com/uploads/2020/12/08/h.png
Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries =
[[0,1,2],[0,2,5]]
Output: [false,true]
Explanation:
query [0,1,2]: 0到1的路径没有一条全部 edges 都小于 2
query [0,2,5]: 有一条 0->1 (权重2), 1->2 (权重4)
Example 2:
https://assets.leetcode.com/uploads/2020/12/08/q.png
Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries =
[[0,4,14],[1,4,13]]
Output: [true,false]
思路:
1.可以把加边和查 query 的事件一起排序，用 edge weight 当 key
如果对某个 query 的 limit 来说，所有比 limit 小的边都已经加到 graph 上了
那就能直接看他 query 的起始结束点是不是 connected 就好
2.看有没有 connected 可以直接用 disjoint set
加边就是 union 两点
排事件点的时候要把 query 排在加边前面(因为目前可用的边的权重要<limit)
Python code:
class Solution:
def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]],
queries: List[List[int]]) -> List[bool]:
root = list(range(n))
def find(x):
if root[x] != x:
root[x] = find(root[x])
return root[x]
events = []
for edge in edgeList:
events.append(edge+[inf])
for i, query in enumerate(queries):
events.append(query+[i])
events.sort(key = lambda x: (x[2], x[3]))
res = [0]*len(queries)
for event in events:
ra, rb = find(event[0]), find(event[1])
if event[3] == inf:
root[ra] = rb
else:
res[event[3]] = (ra == rb)
return res