AcWing 859. Kruskal算法求最小生成树
原题链接
简单
kruskal算法,适用于稀疏图求最小生成树(因为排序的时间与边数有关)
import java.util.*;
public class Main {
static final int N = 100010;
static final int M = 200010;
static final int INF = 0x3f3f3f3f;
static int n;
static int m;
static int[] p = new int[N];
static class Edge {
int a;
int b;
int w;
Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
public String toString() {
return "a = " + a + " b = " + b + " w = " + w;
}
}
static Edge[] edges = new Edge[M];
private static int find(int x) { // 并查集的模板,查找节点x的祖宗节点+路径压缩优化
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
private static int kruskal() {
Arrays.sort(edges, 0, m, (Edge edge1, Edge edge2) -> edge1.w - edge2.w);
for (int i = 1; i <= n; i++) p[i] = i; // 并查集的初始化,不要忘了!
int res = 0;
int cnt = 0;
for (int i = 0; i < m; i++) {
int a = edges[i].a;
int b = edges[i].b;
int w = edges[i].w;
a = find(a);
b = find(b);
if (a != b) {
p[a] = b;
res += w;
cnt++;
}
}
if (cnt < n - 1) return INF; // 如果是连通图,边的个数一定等于n - 1
else return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
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);
}
int t = kruskal();
if (t == INF) System.out.println("impossible");
else System.out.println(t);
}
}