题解 | #最小生成树#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
    blank     * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    public static class UnionFindSet {
        //一维数组elem存储的是下标节点的父节点的下标
        //例如 x的根节点是y，则elem[x]=y
        //节点对应不一定是下标可以根据具体的需求做具体的改进
        private final int[] elem;
        //构造方法
        //根据构造数组，并利用fill充满数组为-1，代表初始化时指向节点自身，且其绝对值为该集合中元素的个数
        public UnionFindSet(int n) {
            this.elem = new int[n];
            Arrays.fill(this.elem, -1);
        }
        public int findRoot(int x) {
            //递归找寻根节点
           while(elem[x] >= 0){
                x = elem[x];
        }
            return x;
        }
        //集合合并
        public void union(int x1, int x2) {
            int index1 = findRoot(x1);
            int index2 = findRoot(x2);

            //将x2加入x1所在的集合中
            elem[index1] += elem[index2];
            elem[index2] = index1;
        }
        //判断是否在一个集合内
        public boolean  isSameSet(int x1, int x2) {
            return findRoot(x1) == findRoot(x2);
        }

    }
    static 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;
        }
    }
    // write code here
    public int miniSpanningTree(int n, int m, int[][] cost) {
        //使用优先级队列存放所有的边
        PriorityQueue<Edge> minHeap = new PriorityQueue<Edge>(
            (a, b)->a.weight - b.weight);
        for (int[] c : cost) {
            minHeap.offer(new Edge(c[0], c[1], c[2]));
        }
        //最终的权值和
        int retWeight = 0;
        //定义并查集
        UnionFindSet unionFindSet = new UnionFindSet(m + 1);
        while (!minHeap.isEmpty()) {
            Edge minEdge = minHeap.poll();
            int src = minEdge.src;
            int dest = minEdge.dest;
            //如果src和dest同根,不能添加
            if (!unionFindSet.isSameSet(src, dest)) {
                unionFindSet.union(src, dest);
                retWeight += minEdge.weight;
            }
        }
        return retWeight;
    }
}