---

1135. 最低成本连通所有城市

• 标签：并查集、图、最小生成树、堆（优先队列）
• 难度：中等

题目链接

• 1135. 最低成本连通所有城市 - 力扣

题目大意

描述：想象你是城市规划师，有 $n$ 座城市（编号 1 到 $n$）。给你一些可以修建的道路信息 $connections$，每条路 $[x_i, y_i, cost_i]$ 表示可以在城市 $x_i$ 和 $y_i$ 之间修一条路，花费 $cost_i$。

要求：用最低的总成本修建一些道路，使得所有城市之间都能连通（可以直接通也可以通过其他城市中转）。如果无法连通所有城市，返回 $-1$。

说明：

• $1 \le n \le 10^4$。
• $1 \le connections.length \le 10^4$。
• $connections[i].length == 3$。
• $1 \le x_i, y_i \le n$。
• $x_i \ne y_i$。
• $0 \le cost_i \le 10^5$。

示例：

• 示例 1：

输入：n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
输出：6
解释：选 1-2（5）和 2-3（1）共 6 元，或者选 1-3（6）和 2-3（1）共 7 元，前者更便宜。

• 示例 2：

输入：n = 4, connections = [[1,2,3],[3,4,4]]
输出：-1
解释：城市 2 和 4 连不到一起，没法连通所有城市。

解题思路

思路 1：Kruskal 算法（最小生成树）

这个问题本质上是最小生成树问题。想象你在修建路网，目标是让所有城市都连通，同时总花费最小。

直观的策略是：每次都选最便宜且不会造成浪费的路线。

这个策略在算法上叫 Kruskal 算法。它的核心思想就是贪心 —— 把修路看作「从零开始，逐渐把所有城市串在一起」的过程。具体来说：

先介绍一下并查集： 并查集（Union-Find）是一个用来管理「元素分组」的数据结构。可以把它想象成「朋友圈」—— 一开始每个人都是独立的圈子，当两个人认识后，他们的圈子就合并成了一个。用它来检查两个城市是不是已经连通非常方便。

步骤拆解：

1. 先把所有道路按价格从低到高排序。 这样最便宜的路会排在前面，优先考虑。

2. 初始化并查集。 一开始每个城市都是一个独立的圈子。用一个 parent 数组记录每个城市的「老大」是谁。

3. 从最便宜的道路开始遍历。 对于每条道路 (x, y, cost)：

   • 用并查集检查城市 $x$ 和 $y$ 是否已经连通（是不是在同一个圈子）。
   • 如果还没连通： 这条路有用！把它加入我们的修路计划，总花费加上 cost，然后把 $x$ 和 $y$ 所在的圈子合并。
   • 如果已经连通： 跳过这条路（再修一条就是浪费钱）。

4. 提前结束。 如果已经修了 $n-1$ 条路，说明所有城市已经连通了（$n$ 个城市连成一片最少需要 $n-1$ 条路），直接返回总花费。

5. 检查结果。 如果遍历完所有可能的路后，修的路还不到 $n-1$ 条，说明有些城市永远连不上，返回 $-1$。

为什么 Kruskal 算法能得到最优解？
因为它的核心是「每次选最便宜的可用路」。可以用反证法证明：如果在最优方案中有一条更便宜的路没选，换成那条更便宜的路只会让总成本更低，所以「每次都选最便宜的」必然是最优的。

思路 1：代码

class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:
        # 并查集的三个操作
        
        # 初始化：每个城市的「老大」就是自己
        parent = list(range(n + 1))  # 下标从 1 开始，所以长度是 n+1
        
        def find(x):
            """找到 x 所在圈子的「老大」"""
            if parent[x] != x:
                parent[x] = find(parent[x])  # 路径压缩：让每个人的老大直接指向根老大
            return parent[x]
        
        def union(x, y):
            """合并 x 和 y 所在的圈子，如果本来就在一起，返回 False"""
            root_x = find(x)
            root_y = find(y)
            if root_x != root_y:
                parent[root_x] = root_y  # 让 x 圈子的老大认 y 圈子的老大当老大
                return True  # 合并成功
            return False  # 已经在同一个圈子了
        
        # 第 1 步：把所有道路按价格从低到高排序
        connections.sort(key=lambda x: x[2])
        
        total_cost = 0     # 总花费
        edges_used = 0     # 已经选了多少条路
        
        # 第 2 步：从最便宜的路开始，逐个检查
        for x, y, cost in connections:
            # 如果 x 和 y 还没连通，这条路就是有用的
            if union(x, y):
                total_cost += cost   # 加上这条路的花费
                edges_used += 1      # 已选道路数 +1
                # 第 3 步：如果已经选了 n-1 条路，所有城市都连通了
                if edges_used == n - 1:
                    return total_cost
        
        # 第 4 步：遍历完了还连不通所有城市，返回 -1
        return -1

思路 1：复杂度分析

• 时间复杂度：$O(m \log m)$。用人话说就是：主要时间花在给道路排序上（$m$ 是道路数量），排序之后每条路只要常数时间判断一次即可。
• 空间复杂度：$O(n)$。需要一个长度为 $n$ 的数组来维护并查集。