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

Categories:

题目描述
思路分析
1. 解法一：最小生成树（推荐）
相似题目

题目描述

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

思路分析

解法一：最小生成树（推荐）

核心思路：

使用 Kruskal 算法按边权排序并逐条尝试连接。

通过并查集合并城市，统计已连接的边数。

若最终连通所有城市，返回总权重，否则返回 -1。

复杂度分析：

时间复杂度：O(m log m)，其中 m 表示边数。

空间复杂度：O(n)，用于并查集。

import java.util.Arrays;

class Solution {
    public int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);

        UnionFind uf = new UnionFind(n + 1);
        int cost = 0;
        int edges = 0;

        for (int[] e : connections) {
            if (uf.union(e[0], e[1])) {
                cost += e[2];
                edges++;
            }
        }

        return edges == n - 1 ? cost : -1;
    }

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

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

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

        boolean union(int a, int b) {
            int ra = find(a);
            int rb = find(b);
            if (ra == rb) {
                return false;
            }
            if (rank[ra] < rank[rb]) {
                parent[ra] = rb;
            } else if (rank[ra] > rank[rb]) {
                parent[rb] = ra;
            } else {
                parent[rb] = ra;
                rank[ra]++;
            }
            return true;
        }
    }
}

import "sort"

func minimumCost(n int, connections [][]int) int {
	sort.Slice(connections, func(i, j int) bool {
		return connections[i][2] < connections[j][2]
	})

	uf := newUnionFind(n + 1)
	cost := 0
	edges := 0

	for _, e := range connections {
		if uf.union(e[0], e[1]) {
			cost += e[2]
			edges++
		}
	}

	if edges == n-1 {
		return cost
	}
	return -1
}

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

func newUnionFind(n int) *unionFind {
	parent := make([]int, n)
	rank := make([]int, n)
	for i := 0; i < n; i++ {
		parent[i] = i
	}
	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(a int, b int) bool {
	ra := uf.find(a)
	rb := uf.find(b)
	if ra == rb {
		return false
	}
	if uf.rank[ra] < uf.rank[rb] {
		uf.parent[ra] = rb
	} else if uf.rank[ra] > uf.rank[rb] {
		uf.parent[rb] = ra
	} else {
		uf.parent[rb] = ra
		uf.rank[ra]++
	}
	return true
}

相似题目

题目	难度	考察点
1135. 最低成本连通所有城市	中等	最小生成树
1584. 连接所有点的最小费用	中等	最小生成树
684. 冗余连接	中等	并查集
743. 网络延迟时间	中等	最短路
778. 水位上升的泳池中游泳	困难	最小生成树

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/74255171