Kruskal算法求最小生成树

给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入格式

第一行包含两个整数n和m。

接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。

输出格式

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。

数据范围

$1 \leq n \leq 10^5,1 \leq m $

$1 \leq m \leq 2*10^5$
图中涉及边的边权的绝对值均不超过1000。

输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

思考方向：Kruskal算法只有两步

第一步：将所有的边按照权重值排序

第二步：按照顺序遍历点，然后如果该组的两个点没有联通，那就将其联通，并且用cnt记录边的条数，用res+=c记录边的数字总大小

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @author zhouyanxiang
 * @Date 2021-03-2021/3/16-21:01
 */
public class Main {

    private static int N = 100010;
    private static int M = 200010;
    private static int max = (int) 1e9;
    private static int[] p = new int[N];
    private static int n,m;
    static Comparator<Node> cmp = new Comparator<Node>() {
        @Override
        public int compare(Node o1, Node o2) {
            return o1.c - o2.c;
        }
    };

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] arr1 = reader.readLine().split(" ");
        n = Integer.parseInt(arr1[0]);
        m = Integer.parseInt(arr1[1]);
        Node[] edges = new Node[m];
        for (int i = 0; i < m; i++) {
            String[] arr = reader.readLine().split(" ");
            int a = Integer.parseInt(arr[0]);
            int b = Integer.parseInt(arr[1]);
            int c = Integer.parseInt(arr[2]);
            edges[i] = new Node(a,b,c);
        }

        Arrays.sort(edges,cmp);
        // 初始化
        for (int i = 1; i <= n; i++) {
            p[i] = i;
        }
        int cnt = 0;
        int res = 0;
        for (int i = 0; i < m; i++) {
            Node t = edges[i];
            int a1 = t.a;
            int b1 = t.b;
            int c1 = t.c;
            int fa = find(a1);
            int fb = find(b1);
            if (fa != fb) {
                p[fa] = fb;
                cnt++;
                res+=c1;
            }
            // 需要选中n-1条边构成树
            if (cnt == n - 1) {
                break;
            }
        }
        if (cnt == n - 1) {
            writer.write(res + "\n");
        } else {
            writer.write("impossible");
        }
        writer.flush();
        writer.close();
        reader.close();
    }

    private static class Node {
        private int a;
        private int b;
        private int c;
        public Node(int a,int b,int c) {
            super();
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }

    private static int find(int x) {
        // 只要x和它的父类p[x]不联通，那就将x的父类p[x]一直往上联通p[p[x]]，并且使得x = p[x]
        while (x != p[x]) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }


}