题解 | #最小生成树#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */

    //并查集的定义
    class UnionFind {

        //定义一个parents数组来追溯是否包含集合内
        private int[] parents;

        //传入点的个数来初始化parents
        public UnionFind(int n) {
            this.parents = new int[n];
            //初始化时每个点按顺序对应自己的下标映射（假设顶点从1开始），每个点对应下标对应parents中自己的下标值
            //也可以说初始化时候每个点顶都属于自己的独立集合不依赖不映射任何一个顶点
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }
        }

        public int find(int index) {
            //函数传入要查找点下标对应parents中的下标值
            //如果该点下标索引对应的值与自己的下标值不对应，
            // 那就说明这个点已经加入了其他点的集合，
            // 它现在索引对应的值就是它依赖点的下标值
            if (parents[index] != index) {
                //那样的话就递归寻找它最终依赖的那个点的下标并且写入它现在的索引位置
                //递归的出口就是最终大家都依赖的那个点，它对应的下标索引还是自己
                parents[index] = find(parents[index]);
            }
            //把索引到的该点依赖的点的下标返回（自己依赖自己那就原值返回）
            return parents[index];
        }


        public boolean isContain(int beginIndex, int endIndex) {
            //查找现在要加入这条边的起点和终点是否在同一个依赖集合，如果在一起那就会形成环
            return find(beginIndex) == find(endIndex);
        }

        public void union(int beginIndex, int endIndex) {
            if (!isContain(beginIndex, endIndex)) {
                //如果这条边起点和终点不在同一个依赖集合，那就把现在的起点加入终点的依赖集合
                parents[find(beginIndex)] = find(
                                                endIndex);//现在目前这个树中所有的点都
                // 依赖于现在的终点find(endIndex)
            }
        }
    }
//边类定义
    class Edge {
        int src;
        int dest;
        int weight;

        public Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        List<Edge> edgeList = new ArrayList<>();
        for (int[] edge : cost) {
            edgeList.add(new Edge(edge[0] - 1, edge[1] - 1, edge[2]));
        }

        // 按边的权重从小到大排序
        edgeList.sort(Comparator.comparingInt(e -> e.weight));

        UnionFind uf = new UnionFind(n);
        int mstWeight = 0;

        for (Edge edge : edgeList) {
            if (!uf.isContain(edge.src, edge.dest)) {
                uf.union(edge.src, edge.dest);
                mstWeight += edge.weight;
            }
        }

        return mstWeight;
    }
}