解释一下这段代码并说出它的计算复杂度import java.util.Arrays; import java.util.Scanner; public class p1160 { static class Node implements Comparable<Node> { int x, y, len; public Node(int x, int y, int len) { this.x = x; this.y = y; this.len = len; } @Override public int compareTo(Node other) { return Integer.compare(this.len, other.len); } } static int[] fa; static int find(int x) { if (fa[x] != x) fa[x] = find(fa[x]); return fa[x]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); fa = new int[n + 1]; for (int i = 1; i <= n; i++) fa[i] = i; Node[] p = new Node[m + 1]; for (int i = 1; i <= m; i++) { int x = scanner.nextInt(); int y = scanner.nextInt(); int len = scanner.nextInt(); p[i] = new Node(x, y, len); } Arrays.sort(p, 1, m + 1); int s = 0, maxz = 0; int i; for (i = 1; i <= m && s < n - 1; i++) { int tx = find(p[i].x); int ty = find(p[i].y); if (tx != ty) { fa[tx] = ty; s++; maxz = Math.max(maxz, p[i].len); } } System.out.println(maxz); System.out.println(i - 1); for (int j = 1; j < i; j++) System.out.println(p[j].x + " " + p[j].y); } }
时间: 2024-01-27 20:02:58 浏览: 78
java代码-import java.util.Scanner;
5星 · 资源好评率100%
这段代码实现了一个最小生成树算法,采用的是Kruskal算法。输入的第一行包含两个整数n和m,分别表示点的个数和边的个数。接下来m行每行包含三个整数x、y、len,表示点x和点y之间有一条长度为len的边。程序会输出最小生成树的最大边权值,以及最小生成树的所有边。
该算法的时间复杂度为O(mlogm),其中m是边的数量。主要由于排序的时间复杂度为O(mlogm)。
阅读全文