AcWing 859. Kruskal算法求最小生成树
原题链接
简单
作者:
gongjin
,
2023-01-03 17:25:23
,
所有人可见
,
阅读 105
kruskal算法求最小生成树 JAVA实现
import java.util.Arrays;
import java.util.Scanner;
class Edge {
int a;
int b;
int w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
}
class Main {
static int N = 200010;
static Edge[] edges;
static int[] p = new int[N];
static int n;
static int m;
static int res = 0;
static int cnt = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
edges = new Edge[m];
for (int i = 1; i <= n; i++) {
p[i] = i;
}
for (int i = 0; i < m; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
int w = scanner.nextInt();
edges[i] = new Edge(a, b, w);
}
Arrays.sort(edges, (a, b) -> a.w - b.w);
if (kruskal()) {
System.out.println(res);
} else {
System.out.println("impossible");
}
}
public static int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static boolean kruskal() {
for (int i = 0; i < m; i++) {
Edge edge = edges[i];
int a = edge.a;
int b = edge.b;
int w = edge.w;
a = find(a);
b = find(b);
if (a != b) {
p[a] = b;
res += w;
cnt++;
}
}
if (cnt < n - 1) {
return false;
} else {
return true;
}
}
}