10-Kruskal算法

算法思想

算法模板

import java.util.*;

public class Main {
    static int N = 100010, M = 200010, INF = 0x3f3f3f3f;
    static int n, m;
    static boolean[] st = new boolean[N];
    static PriorityQueue<Edge> q = new PriorityQueue<Edge>(Comparator.comparing(e -> e.weight));
    static int[] p = new int[N], w = new int[N], cnt = new int[N];
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1; i <= n; i ++ )
        {
            p[i] = i;
            cnt[i] = 1;
        }
        
        while(m -- > 0)
        {
            int x = in.nextInt(), y = in.nextInt();
            int weight = in.nextInt();
            q.offer(new Edge(x, y, weight));
        }
        
        int t = kruskal();
        if(t == INF) System.out.println("impossible");
        else System.out.println(t);
    }
    
    static int kruskal()
    {
        int res = 0, cnt = 0;
        while(!q.isEmpty())
        {
            Edge e = q.poll();
            
            int x = e.from, y = e.to;
            int rx = find(x), ry = find(y);
            // 合并的次数
            // 若合并了 n - 1 次，则说明 n 个节点是个连通集
            if(rx != ry)
            {
                p[ry] = rx;
                res += e.weight;
                cnt ++ ;
            }
        }
        
        if(cnt < n - 1) return INF;
        else return res;
    }
    
    static int find(int x)
    {
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

class Edge
{
    int from, to, weight;
    public Edge(int from, int to, int weight)
    {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}