3、Kruskal最小生成树 &并查集

AcWing 859. Kruskal算法求最小生成树

Kruskal算法更适合稀疏图

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main { 
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    int n, m;
    int N = 2000010;
    int pp[] = new int[N];
    Edge[] edges = new Edge[N];

    int find(int x) {
        if (x != pp[x]) pp[x]= find(pp[x]);
        return pp[x];
    }

    class Edge implements Comparable {
        int a, b, w;

        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }

        @Override
        public int compareTo(Object o) {
            Edge edge = (Edge) o;
            return w - edge.w;
        }
    }

    int edge_sums = 0;
    int cnt = 0;

    void kruskal() {
        for (int i = 0; i < m; i++) {
            Edge edge = edges[i];
            int f_a = find(edge.a);
            int f_b = find(edge.b);
            if (f_a != f_b) {
                edge_sums += edge.w;
                pp[f_a] = f_b;
                cnt++;
            }
        }
    }

    void init() {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <=n; i++) {
            pp[i] = i;//初始化的时候，i的祖宗就是i自己
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int w = sc.nextInt();
            edges[i] = new Edge(a, b, w);
        }
        Arrays.sort(edges,0,m);
        kruskal();
        if (cnt < n-1) System.out.println("impossible");
        else
            System.out.println(edge_sums);
    }
}