最小生成树

• OI Wiki: https://oi-wiki.org/graph/mst/

题目	难度
$1135. 最低成本联通所有城市	中等
$1168. 水资源分配优化	困难
1489. 找到最小生成树里的关键边和伪关键边	困难	推荐
1584. 连接所有点的最小费用	中等

Kruskal 算法

前置知识：并查集、贪心、图的存储。

$1135. 最低成本联通所有城市

import java.util.Arrays;
import java.util.Comparator;

public class Solution1135 {
    public int minimumCost(int n, int[][] connections) {
        // Kruskal 算法
        Arrays.sort(connections, Comparator.comparing(o -> o[2]));
        // 并查集
        DSU dsu = new DSU(n + 1);
        dsu.sz = n;
        int cost = 0;
        for (int[] connection : connections) {
            if (!dsu.union(connection[0], connection[1])) {
                cost += connection[2];
            }
        }
        if (dsu.sz != 1) {
            return -1;
        }
        return cost;
    }

    private static class DSU {
        int[] fa;
        int sz;

        public DSU(int n) {
            fa = new int[n];
            for (int i = 0; i < n; i++) {
                fa[i] = i;
            }
        }

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

        boolean union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) {
                return true;
            }
            fa[rootQ] = rootP;
            sz--;
            return false;
        }
    }
}

（全文完）