给出一幅无向图,一共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