题目链接：P3366 MST

思路是利用Union-Find并查集和PriorityQueue来实现Kruskal算法求最小生成树

判断图是否连通部分isConnected()是利用BFS算法遍历所有数据点判断图是否连通

数据点总是过不了 7个WA 3个MLE 3个AC

以下是java代码：

import java.util.*;

class UnionFind {

    private final int[] elements;

    public UnionFind(int size) {
        elements = new int[size];
        for (int i = 0; i < elements.length; i++) {
            elements[i] = i;
        }
    }

    public int find(int i) {
        while (elements[i] != i) {
            i = elements[i];
        }
        return i;
    }

    public void union(int i, int j) {
        elements[find(i)] = find(j);//i的祖宗的祖宗是j的祖宗
    }
}






class Edge implements Comparable<Edge> {
    public final int i, j, weight;

    public Edge(int i, int j, int weight) {
        this.i = i;
        this.j = j;
        this.weight = weight;
    }


    @Override
    public int compareTo(Edge o) {return weight - o.weight;}
}



public class Main {
    static boolean isConnected(int[][] graph){ //点1,2,...,vertices
        int count = 1;
        //从1开始找
        //假设0是无路
        int currentNode = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[graph.length];
        for (int i = 0; i < graph.length; i++) {
            visited[i] = false;
        }

        queue.offer(0);
        visited[0] = true;
        while(!queue.isEmpty()){
            currentNode = queue.poll();
            for (int i = 0; i < graph.length; i++) {
                if(graph[currentNode][i] != Integer.MAX_VALUE && !visited[i]){
                    queue.offer(i);
                    visited[i] = true;
                    count++;
                }
            }
        }

        if(count == graph.length){
            return true;
        } else {
            return false;
        }
    }
  
    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] map = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(map[i], Integer.MAX_VALUE);
        }
        for (int i = 1; i <= M; i++) {
            int s = sc.nextInt();
            int d = sc.nextInt();
            map[s-1][d-1] = sc.nextInt(); //表示的是点s到点d的距离
            map[d-1][s-1] = map[s-1][d-1];
        }
        if(isConnected(map)){
            System.out.println(kruskal(map));
        } else {
            System.out.println("orz");
        }
    }

    public static int kruskal(int[][] map) {
        /**
         * 并查集，检测两个点是否已经属于同一棵树
         */
        UnionFind unionFind = new UnionFind(map.length); //n^2大小的邻接矩阵 其包含n个点的信息
        /**
         * 待选择的边，放入优先队列排序
         */
        Queue<Edge> edgeQueue = new PriorityQueue<>();
       
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < i; j++) {
                if(map[i][j] != INF){
                    edgeQueue.offer(new Edge(i,j,map[i][j]));
                }
            }
        }
        /**
         * 总路径长度
         */
        int sum = 0;
        /**
         * 当前已选择边的数量
         */
        int count = 0;
        while (count < map.length - 1) { //map.length是总点数 总点数-1是边数 但当前 边数=总点数-1 时表示边已经选完 不用再选 于是是小于号
            Edge edge = edgeQueue.poll();
            /**
             * 检测边的两个顶点是否已经在同一棵树中
             */
            if (unionFind.find(edge.i) == unionFind.find(edge.j)) {
                continue;
            }
            count++;
            sum += edge.weight;
            /**
             * 将两个顶点所在的树在并查集中合并
             */
            unionFind.union(edge.i, edge.j);
        }
        return sum;
    }
}