Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一幅无向图,一共n个节点,问是否可以通过改变其中的若干边使得所有节点联通
首先判断图中边数是否>n-1,不满足的话不可能联通
符合条件的话求连通分量个数ncc,输出ncc-1


 1 #1319
 2 #Runtime: 1542 ms (Beats 70.59%)
 3 #Memory: 73.7 MB (Beats 58.82%)
 4 
 5 class Solution(object):
 6     def minScore(self, n, roads):
 7         """
 8         :type n: int
 9         :type roads: List[List[int]]
10         :rtype: int
11         """
12         edge = defaultdict(list)
13         ans = 0
14         for x, y, w in roads:
15             edge[x].append((y, w))
16             edge[y].append((x, w))
17             ans += w
18         q = deque([1])
19         vis = [0] * (n + 1)
20         vis[1] = 1
21         while q:
22             x = q.popleft()
23             for y, w in edge[x]:
24                 if not vis[y]:
25                     q.append(y)
26                 vis[y] = 1
27                 ans = min(ans, w)   
28         return ans

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