Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一个无向图最多100000个节点,每条边给出相应的距离,有最多100000次询问,每次询问x和y节点之间是否存在一条路,路上所有边的距离都小于(不包含等于)limit。并查集的应用,在合并和查找时增加对dis的维护和判断


 1 #1697
 2 #Runtime: 1668 ms (Beats 100%)
 3 #Memory: 59.9 MB (Beats 100%)
 4 
 5 class Solution(object):
 6     def distanceLimitedPathsExist(self, n, edgeList, queries):
 7         """
 8         :type n: int
 9         :type edgeList: List[List[int]]
10         :type queries: List[List[int]]
11         :rtype: List[bool]
12         """
13         parent = [i for i in range(n)]
14         rank = [i for i in range(n)]
15         def find(x, limit):
16             while x != parent[x]:
17                 if dis[x] >= limit:
18                     break
19                 x = parent[x]
20             return x
21 
22         def union(x, y, d):
23             fa = find(x, float('inf'))
24             fb = find(y, float('inf'))
25             if fa != fb:
26                 if rank[fa] < rank[fb]:
27                     parent[fa] = fb
28                     dis[fa] = d
29                 else:
30                     parent[fb] = fa
31                     dis[fb] = d
32                     if rank[fa] == rank[fb]:
33                         rank[fa] += 1
34 
35         def judge(x, y, limit):
36             return find(x, limit) == find(y, limit)
37 
38         dis = [0 for _ in range(n)]
39         edgeList.sort(key=lambda x: x[2])
40         for ed in edgeList:
41             union(ed[0], ed[1], ed[2])
42         ans = []
43         for q in queries:
44             ans.append(judge(q[0], q[1], q[2]))
45         return ans

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理