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