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

2024-11-10 HGNULB 约 12 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

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

题意分析

给定 n 座编号从 1 到 n 的城市，以及一批「连接城市 a 和 b 需要花费 cost」的候选连接，要求挑出一个花费总和最小的子集，使得任意两座城市之间都能互相到达。注意连接是双向的，且题目只关心连通性而不关心具体路径长度，这两点决定了它是一个无向图上的选边问题，而不是最短路问题。

「让所有点连通」和「总权重最小」这两个要求同时出现，是一个非常明确的信号。要连通 n 个点至少需要 n - 1 条边，而只要选出的边数恰好是 n - 1 且不成环，图就必然连通；反过来，任何多余的边都只会白白增加成本。所以答案一定是一棵包含全部 n 个点、边数为 n - 1 的树，问题就变成在所有这样的树里挑权重和最小的那一棵。

输入里的城市编号从 1 开始而不是从 0 开始，这个细节会直接影响辅助数组的开辟大小，是本题最常见的翻车点。另外候选连接可能包含权重不同的重复边，也可能整体就不足以连通所有城市。

边界要单独想：候选边数少于 n - 1 时无论怎么选都不可能连通，必须返回 -1；即使边数够多，也可能全部集中在某几座城市之间，导致剩下的城市成为孤岛，同样返回 -1；多条边成本相同时任选其一都不影响最优总成本，不需要额外的打破平局规则。

解法：Kruskal + 并查集

核心思路

暴力做法是枚举所有 n - 1 条边的组合，检查是否连通并取最小总成本，组合数是指数级的，完全不可行。稍微聪明一点的做法是随便先造一棵生成树再尝试换边优化，但「换哪条边能变小」本身又是一个需要遍历环上所有边的子问题，瓶颈在于每次判断都要重新分析全图结构。

关键观察来自一条可以直接证明的性质：把所有边按成本从小到大排序后，依次考察每条边，如果它连接的两个端点当前还不连通，那么这条边一定属于某棵最小生成树。直觉上讲，此时这两个连通块之间迟早要用一条边接上，而所有还没被考察的边成本都不小于它，用它接上不会比用任何别的边更差。这条性质把全局最优化问题拆成了一串独立的局部决策，贪心因此成立。

于是维护的不变量是：已选边的集合在任何时刻都是一个无环子图（即若干棵树构成的森林），并且它是「只使用已考察过的这些边」时能达到的最优森林。要维持这条不变量，每一步只需要回答一个问题——当前边的两个端点是否已经在同一棵树里。

回答这个问题的数据结构就是并查集：每个连通块用一个代表元标识，find 沿父指针一路上溯找到代表元，union 把两个代表元挂在一起。端点代表元相同说明加入这条边会成环，直接跳过；不同则合并并累加成本。同时用 edgeCount 记录已选边数，一旦达到 n - 1 就说明森林已经收缩成一棵覆盖全部城市的树，可以立即返回；循环自然结束时仍未达到，说明图本身不连通，返回 -1。

解题步骤

第一步，按第三个分量对 connections 升序排序。这是整个贪心的前提：只有从小到大考察，才能保证「第一条能连上两个不同连通块的边」就是这两块之间的最优选择。用 Integer.compare 而不是相减做比较，是为了避免成本差值在极端取值下发生整型溢出导致比较结果反号。

第二步，初始化容量为 n + 1 的并查集，并把答案 answer 和已选边数 edgeCount 清零。容量必须是 n + 1 而不是 n，因为城市编号是 1 到 n，下标 n 必须是合法的；多出来的 0 号位置永远不会被访问，浪费一个槽位换来编号无需平移，代码更不容易出错。

第三步，顺序遍历排好序的边，取出两端城市和成本，调用 union。这里把「判环」和「合并」合并进同一个方法并让它返回布尔值，是一个值得养成的习惯：返回 false 表示两点本就连通，这条边被丢弃；返回 true 表示合并成功，此时才累加成本并把边数加一。分成 find 两次再比较再 union 的写法会重复走一遍路径，逻辑也更容易漏掉某个分支。

第四步，每次成功合并后检查 edgeCount 是否等于 n - 1，成立就立刻返回 answer。提前返回的意义不只是省时间，更是表达「树已经建成」这个语义；如果一直没有触发，循环结束后返回 -1，说明所有候选边都考察完了仍有城市没被并进来。

并查集内部两处细节值得说明：find 里的 parent[x] = find(parent[x]) 是路径压缩，它在回溯时把整条查询路径上的节点全部直接挂到根上，让后续查询几乎是常数时间；union 里按 rank 决定谁挂谁，是为了避免树高线性增长，两者配合才能得到近乎常数的均摊复杂度。注意 rank 只在两棵树高度相等时才加一，因为只有这种情况下合并才真的让树长高了一层。

以 n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]] 走一遍：排序后边的顺序变成 [2,3,1]、[1,2,5]、[1,3,6]。第一条边连接 2 和 3，此时 find(2) = 2、find(3) = 3 不相等，合并成功（rank 相等，3 挂到 2 下面且 rank[2] 变 1），answer = 1，edgeCount = 1，还不等于 n - 1 = 2。第二条边连接 1 和 2，find(1) = 1、find(2) = 2 不相等，合并成功（rank[1] 为 0 小于 rank[2] 为 1，所以 1 挂到 2 下面），answer = 1 + 5 = 6，edgeCount = 2，等于 n - 1，立即返回 6。第三条边 [1,3,6] 根本没被考察到——即使考察，find(1) 和 find(3) 都会得到 2，被判成环丢弃。最终答案 6，对应选择 2-3 和 1-2 这两条连接，比选 1-2 和 1-3 的 11 更省。

代码实现

class Solution {
    // Kruskal 按边权从小到大选边，并查集用于判断加入该边是否会成环。
    public int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, (x, y) -> Integer.compare(x[2], y[2]));

        UnionFind uf = new UnionFind(n + 1);
        int answer = 0;
        int edgeCount = 0;

        for (int[] edge : connections) {
            int cityA = edge[0];
            int cityB = edge[1];
            int cost = edge[2];
            if (!uf.union(cityA, cityB)) {
                continue;
            }

            answer += cost;
            edgeCount++;
            if (edgeCount == n - 1) {
                return answer;
            }
        }

        return -1;
    }

    private static class UnionFind {
        private final int[] parent;
        private final int[] rank;

        UnionFind(int size) {
            parent = new int[size];
            rank = new int[size];
            for (int idx = 0; idx < size; idx++) {
                parent[idx] = idx;
            }
        }

        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return false;
            }
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }

            return true;
        }
    }
}

func minimumCost(n int, connections [][]int) int {
    // Kruskal 按边权从小到大选边，并查集用于判断加入该边是否会成环。
    sort.Slice(connections, func(i int, j int) bool {
        return connections[i][2] < connections[j][2]
    })

    uf := newUnionFind(n + 1)
    answer := 0
    edgeCount := 0

    for _, edge := range connections {
        cityA, cityB, cost := edge[0], edge[1], edge[2]
        if !uf.union(cityA, cityB) {
            continue
        }

        answer += cost
        edgeCount++
        if edgeCount == n-1 {
            return answer
        }
    }

    return -1
}

type unionFind struct {
    parent []int
    rank   []int
}

func newUnionFind(size int) *unionFind {
    parent := make([]int, size)
    rank := make([]int, size)
    for idx := 0; idx < size; idx++ {
        parent[idx] = idx
    }
    return &unionFind{parent: parent, rank: rank}
}

func (uf *unionFind) find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *unionFind) union(x int, y int) bool {
    rootX := uf.find(x)
    rootY := uf.find(y)
    if rootX == rootY {
        return false
    }
    if uf.rank[rootX] < uf.rank[rootY] {
        uf.parent[rootX] = rootY
    } else if uf.rank[rootX] > uf.rank[rootY] {
        uf.parent[rootY] = rootX
    } else {
        uf.parent[rootY] = rootX
        uf.rank[rootX]++
    }

    return true
}

复杂度分析

时间复杂度：$O(m \log m)$，其中 m 表示候选连接数。排序占据主导，之后对每条边只做一次 union，在路径压缩加按秩合并下单次操作的均摊代价是反阿克曼函数级别，可视为常数，合计 $O(m \log m + m \alpha(n))$ 由排序项主导。

空间复杂度：$O(n)$，并查集的 parent 与 rank 两个数组各占 n + 1 个整数；排序若采用原地实现则不额外占用，find 的递归深度在路径压缩下被压得很浅。

关键点总结

看到「让所有点连通」加「总代价最小」就应当条件反射地想到最小生成树，并立刻把「答案恰好用 n - 1 条边」这个结构性结论说出来。这个结论既是算法的终止条件，也是判定无解的唯一依据。

Kruskal 的正确性靠的是排序后的贪心，而贪心之所以成立是因为「当前最小的跨连通块边一定在某棵最优树里」。面试时把这句话讲清楚，比背出算法名字有用得多。

让 union 返回布尔值，把「是否成环」和「执行合并」统一进一次调用，是并查集题的通用工程习惯。它天然避免了先判后并之间状态被改动的隐患，也让主循环读起来就是算法本身的描述。

路径压缩与按秩合并是两个独立的优化，可以只用其一。面试中若时间紧张，只写路径压缩的版本通常也会被接受，但要能说清两者各自解决什么问题：压缩让查询变浅，按秩让合并不制造高树。

面试视角上，被问到「Kruskal 还是 Prim」时的标准答法是看图的稠密程度：边数远小于点数平方的稀疏图用 Kruskal，因为主要开销在排序 m 条边；接近完全图的稠密图用 Prim 配堆或朴素 $O(n^2)$ 版本更划算。本题给的是显式边列表，Kruskal 是更自然的选择。

编号从 1 开始时把并查集开成 n + 1 是最省心的做法。与其在每次访问时做减一平移，不如多开一个槽位，减少心智负担也减少出错面。

易错点总结

错误写法：并查集容量写成 n → 对用例 n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]，访问下标 3 时直接数组越界抛异常，因为城市编号最大就是 n 本身。

错误写法：排序比较器写成 (x, y) -> x[2] - y[2] → 当成本取到接近整型上下界的极端值时相减溢出，比较结果反号导致边序错乱，选出的生成树不是最小的。

错误写法：忘记排序直接遍历 connections → 对用例 n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]，会先选 1-2 花费 5 再选 1-3 花费 6 得到 11，而正确答案是 6。

错误写法：不判断是否成环，见边就累加成本 → 同一用例会把三条边全部加上得到 12，且边数超过 n - 1，返回值完全失去意义。

错误写法：union 里直接写 parent[x] = y 而不是先 find 到根再挂 → 对用例 n = 4, connections = [[1,2,1],[2,3,1],[3,4,1]]，第二次合并时把已经有父节点的 2 的指针改掉，1 所在的整块被从树上摘下来，最终 edgeCount 计数正确但连通关系已经错乱。

错误写法：合并成功后忘记 edgeCount 自增，只靠成本累加判断 → 对同一用例循环结束时 edgeCount 恒为 0，永远不等于 n - 1，函数返回 -1 而不是 3。

错误写法：终止条件写成 edgeCount == n → 对用例 n = 2, connections = [[1,2,7]]，唯一一条边选完后 edgeCount 是 1 永远到不了 2，返回 -1 而不是 7。

错误写法：union 在两根相同时也返回 true → 成环的边被计入 edgeCount，对用例 n = 3, connections = [[1,2,1],[1,2,2],[2,3,3]] 会在选完前两条边后就以为树建成，返回 3 而不是 4。

错误写法：按秩合并时每次合并都执行 rank[rootX]++ → 秩失去了「树高上界」的含义，退化成合并次数计数，挂接方向随之变得随意，极端链式输入下树高退化，find 变成线性。

错误写法：路径压缩写成 find(parent[x]) 而不把结果赋回 parent[x] → 压缩完全没有生效，对用例中先把 1 到 n 依次两两合并再反复查询的场景，单次 find 退化到 $O(n)$，整体明显变慢。

错误写法：认为「候选边数大于等于 n - 1 就一定连通」，于是省掉最后的 -1 分支 → 对用例 n = 4, connections = [[1,2,1],[1,2,2],[3,4,3]]，边数够但城市 1、2 与 3、4 分成两块，函数会走完循环却没有返回值可给。

相似题目

题目	难度	考察点
1584. 连接所有点的最小费用	中等	边未给出，需先由坐标两两生成曼哈顿距离，稠密图更适合 Prim
1168. 水资源分配优化	困难	打井成本要建模成到虚拟 0 号节点的边，再套同一套 Kruskal
1489. 找到最小生成树里的关键边和伪关键边	困难	需反复做「删边」「强制加边」的 MST 对比，考察对 MST 权值唯一性的理解
1319. 连通网络的操作次数	中等	边无权重，答案退化为连通块数减一，还要先判断线缆是否够用
547. 省份数量	中等	只数连通块个数，不需要排序也不需要累加权重
323. 无向图中连通分量的数目	中等	并查集的最小骨架，可与 DFS 计数解法直接对照
684. 冗余连接	中等	反过来利用 union 返回 false 的时刻定位成环的那条边
721. 账户合并	中等	元素是字符串，需要先做映射再并查集，最后还要按根收集分组
399. 除法求值	中等	带权并查集，find 时要同步维护到根的比值
305. 岛屿数量 II	困难	动态加点，连通块计数需随每次插入实时更新
743. 网络延迟时间	中等	目标是单源最短路而非连通总代价，需用 Dijkstra 而非 MST