难度: Medium
Submission
运行时间: 68 ms
内存: 20.5 MB
class Solution:
def find(self, x, parent):
root = x
while parent[root] > 0:
root = parent[root]
while x != root:
t = x
x = parent[x]
parent[t] = root
return root
def unite(self, rootx, rooty, parent):
if parent[rootx] <= parent[rooty]:
parent[rootx] += parent[rooty]
parent[rooty] = rootx
else:
parent[rooty] += parent[rootx]
parent[rootx] = rooty
def minimumCost(self, n: int, connections: List[List[int]]) -> int:
m = len(connections)
if m < n - 1:
return -1
parent = [-1 for i in range(n + 1)]
count = 0
ans = 0
connections.sort(key=lambda x: x[2])
for i in range(m):
if count == n - 1:
return ans
x = self.find(connections[i][0], parent)
y = self.find(connections[i][1], parent)
if x != y:
self.unite(x, y, parent)
ans += connections[i][2]
count += 1
if count < n - 1:
return -1
return ans
Explain
此题解采用了最小生成树(Kruskal算法)的策略来连接所有城市，要求最小的成本。首先，判断边的数量是否少于n-1，若是，则直接返回-1，因为不可能连接所有城市。使用并查集来维护和查询城市间的连通性。城市和其连接边按照连接成本从低到高排序。遍历排序后的边，使用并查集的find函数来查找每条边两个城市的根节点，如果根节点不同，则使用unite函数合并这两个根节点，并累加当前边的成本到总成本中。当选取的边数达到n-1时，所有城市已经连通，返回累计的最小成本。如果循环结束后，选取的边数仍然少于n-1，则返回-1表示不能连通所有城市。
时间复杂度: O(m log m)
空间复杂度: O(n + m)
class Solution:
def find(self, x, parent):
# 查找并返回元素x的根节点，并进行路径压缩优化
root = x
while parent[root] > 0:
root = parent[root]
while x != root:
t = x
x = parent[x]
parent[t] = root
return root
def unite(self, rootx, rooty, parent):
# 合并两个不同集合的根节点，较小的根节点成为新的根
if parent[rootx] <= parent[rooty]:
parent[rootx] += parent[rooty]
parent[rooty] = rootx
else:
parent[rooty] += parent[rootx]
parent[rootx] = rooty
def minimumCost(self, n: int, connections: List[List[int]]) -> int:
m = len(connections)
if m < n - 1:
return -1 # 边数不足以连接所有城市
parent = [-1 for i in range(n + 1)] # 初始化并查集
count = 0 # 已选择的边数
ans = 0 # 最小成本累计
connections.sort(key=lambda x: x[2]) # 按成本排序边
for i in range(m):
if count == n - 1:
return ans # 已经连通所有城市
x = self.find(connections[i][0], parent)
y = self.find(connections[i][1], parent)
if x != y:
self.unite(x, y, parent)
ans += connections[i][2]
count += 1 # 增加已选择的边数
if count < n - 1:
return -1 # 无法连通所有城市
return ans # 返回最小成本
Explore
路径压缩的主要目的是减少树的高度，从而加速未来对同一组元素的查找操作。在执行查找操作时，路径压缩将沿途的所有节点直接连接到根节点上。这样，下次从这些节点出发的查找操作将直接到达根节点，显著减少查询路径的长度，从而提高效率。
按成本从低到高排序是为了确保每次选取的边是当前可用边中成本最低的，这是Kruskal算法的核心。这种策略保证了算法能找到最小生成树，即连接所有节点的最小总成本。如果不按此方法排序，则可能选取成本较高的边，导致无法达到最小成本的目的。
如果两个城市的根节点相同，意味着它们已经在同一个连通分量中，即已经连通。此时再合并它们是多余的，不会对连通性产生影响。避免这种不必要的合并可以减少算法的冗余操作，保持已有的连通分量不被破坏，同时防止添加多余的成本。
这个结论基于图论中的基本概念。在一个含有n个节点的树中，必须有至少n-1条边才能使所有节点连通而无环。因此，如果一个图中的边数少于n-1，那么至少有一个节点无法通过边与其他节点连通，无法形成一个覆盖所有节点的连通图。因此，边数少于n-1意味着无法连通所有城市。