LeetCode 1135. 最低成本连通所有城市
题目描述
题意分析
城市编号为
1到n，每条可用道路是带成本的无向边。要让任意两个城市之间都有路径，并使选中道路的总成本最小；无法全部连通时返回-1。道路成本非负，连通方案中若出现环，删去环上的一条边仍然连通且不会增加成本，所以总能用一棵生成树达到最优。Kruskal 算法按成本从小到大选边，每次连接两个原本分离的连通块。
解法：Kruskal + 并查集
核心思路
[!blue]
并查集记录已选道路形成的连通块。
find(x)找到城市所在块的代表，路径压缩让沿途节点直接指向代表；union只在两端代表不同时合并，把rank较小的根挂到较大的根下，同秩合并时才把新根的rank加一。两端已经同块时，再选这条边会成环，因此跳过。贪心选择可以用交换说明。设当前边
e连接两个不同块，将其中一个块与其他城市分开；比e更便宜的边已经处理过，不可能还跨过这条分界，否则两端早已合并。若一棵包含已选边的最小生成树没有e，加入e后产生的环中必有另一条跨界边。用e替换那条边不会增加成本，也不会删掉块内已经选定的边，因此仍有一棵最小生成树包含这次选择。
answer累计成功选入的边权，edgeCount统计成功合并次数。初始有n个城市连通块，每次成功合并恰好减少一个块，又始终不成环，所以edgeCount == n-1就意味着全部城市已经连通，可以返回总成本。如果所有边处理完仍不足
n-1次合并，剩余连通块之间没有可用道路，返回-1。最后再次检查边数，也让只有一个城市、没有道路时返回零。数组开到n+1是为了直接使用城市编号，下标零不参与城市的连通判断。
解题步骤
- 边按成本排序，并查集按城市编号初始化。
- 两端同根跳过，否则合并并累计。
- 选够 n−1 条返回，否则返回负一。
代码实现
class Solution {
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 edgeCount == n - 1 ? answer : -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;
}
}
}
import "sort"
func minimumCost(n int, connections [][]int) int {
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
}
}
// 无环森林已有足够边数，此时所有城市已连通。
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(n+E\log(E+1)+E\alpha(n))$。$E$ 为道路数，三部分分别对应并查集初始化、边排序，以及带路径压缩和按秩合并的并查集操作；$\alpha$ 是反阿克曼函数，增长极慢。
- 空间复杂度：并查集 $O(n)$；Java 对象数组排序另需 $O(E)$，Go 排序栈 $O(\log(E+1))$。
关键点总结
[!green]
- 选边数达到 n−1 的依据是已选边始终构成森林。
- rank 是高度上界，路径压缩后不必等于实际高度。
- 循环结束后仍按已选边数检查连通性，覆盖没有任何合并发生的单城市情形。
易错点总结
[!yellow]
- 未排序就选边，只能得到某棵生成树而非最小。
- 同根边仍计入数量，会在图未连通时提前结束。
- 只看候选边数够不够，无法判断城市是否真的连通。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1584. 连接所有点的最小费用 | 中等 | 同样求最小生成树，原题完整图的边权由曼哈顿距离生成，本题直接给出可用城市道路。 |
| 1168. 水资源分配优化 | 困难 | 把每个村庄建井的选择连到虚拟节点后，原题可转为包含虚拟点的最小生成树。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！