克鲁斯卡尔改进

洛谷

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.*;
public class 克鲁斯卡尔 {
    static class Node{
        public int from;
        public int to;
        public int weight;
    }
    static Node[] edges;
    static int[] parent;
    static int n,m;
    private static int find(int x){
        return x==parent[x]?x:find(parent[x]);
    }
    private static void union(int x,int y){
        int fx=find(x);
        int fy=find(y);
        parent[fx]=fy;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st=new StreamTokenizer(br);
        st.nextToken();n=(int)st.nval;
        st.nextToken();m=(int)st.nval;
        parent=new int[n+1];
        for(int i=1;i<=n;i++){
            parent[i]=i;
        }
        edges=new Node[m];
        for(int i=0;i<m;i++){
            edges[i]=new Node();
        }
        for(int i=0;i<m;i++){
            st.nextToken();int from=(int)st.nval;
            st.nextToken();int to=(int)st.nval;
            st.nextToken();int weight=(int)st.nval;
            edges[i].from=from;
            edges[i].to=to;
            edges[i].weight=weight;
        }
        Arrays.sort(edges,(a, b)->a.weight-b.weight);
        int num=0;
        int sum=0;
        for(int i=0;i<m;i++){
            int from=edges[i].from;
            int to=edges[i].to;
            int weight=edges[i].weight;
            if(find(from)!=find(to)){
                sum+=weight;
                union(from,to);
                num++;
            }
            if(num==n-1){
                break;
            }
        }
        if(num!=n-1){
            System.out.println("orz");
        }
        System.out.println(sum);
    }
}