题解 | 【模板】最小生成树

import java.util.*;
import java.io.*;

public class Main {
    static class Edge {
        int u, v, w, id;
        Edge(int u, int v, int w, int id) {
            this.u = u;
            this.v = v;
            this.w = w;
            this.id = id;
        }
    }

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

        public UnionFind(int size) {
            parent = new int[size + 1];
            rank = new int[size + 1];
            for (int i = 1; i <= size; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

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

        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot == yRoot) return;

            if (rank[xRoot] < rank[yRoot]) {
                parent[xRoot] = yRoot;
            } else if (rank[xRoot] > rank[yRoot]) {
                parent[yRoot] = xRoot;
            } else {
                parent[yRoot] = xRoot;
                rank[xRoot]++;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        Edge[] edges = new Edge[m];
        for (int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int w = in.nextInt();
            edges[i] = new Edge(u, v, w, i + 1);
        }

        Arrays.sort(edges, Comparator.comparingInt((Edge e) -> e.w).thenComparingInt(
                        e -> e.id));

        UnionFind uf = new UnionFind(n);
        List<Integer> selected = new ArrayList<>();
        long sum = 0;

        for (Edge e : edges) {
            if (selected.size() == n - 1) break;
            int uRoot = uf.find(e.u);
            int vRoot = uf.find(e.v);
            if (uRoot != vRoot) {
                uf.union(uRoot, vRoot);
                sum += e.w;
                selected.add(e.id);
            }
        }

        System.out.println(sum);
        StringBuilder sb = new StringBuilder();
        for (int id : selected) {
            sb.append(id).append(' ');
        }
        System.out.println(sb.toString().trim());
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. Edge类：用于存储边的信息，包括两个顶点、权值和输入时的编号。
2. UnionFind类：并查集数据结构，用于高效管理顶点的连通性，支持路径压缩和按秩合并。
3. 主函数：读取输入数据，对边按权值和编号排序，使用并查集逐步构建MST，记录总权值和选中的边，最后输出结果。