給出一幅無向圖，一共n個節(jié)點，問是否可以通過改變其中的若干邊使得所有節(jié)點聯(lián)通
首先判斷圖中邊數(shù)是否>n-1，不滿足的話不可能聯(lián)通
符合條件的話求連通分量個數(shù)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