250521 도시 분할 계획

static class Edge implements Comparable<Edge> {
	int u, v, w;

	Edge(int u, int v, int w) {
		this.u = u;
		this.v = v;
		this.w = w;
	}

	@Override
	public int compareTo(Edge other) {
		return this.w - other.w;
	}
}

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	StringTokenizer st = new StringTokenizer(br.readLine());
	int nodeCount = Integer.parseInt(st.nextToken());
	int edgeCount = Integer.parseInt(st.nextToken());

	int[] parents = new int[nodeCount + 1];
	for (int i = 1; i <= nodeCount; i++) {
		parents[i] = i;
	}

	PriorityQueue<Edge> edgeQueue = new PriorityQueue<>();
	for (int i = 0; i < edgeCount; i++) {
		st = new StringTokenizer(br.readLine());
		int u = Integer.parseInt(st.nextToken());
		int v = Integer.parseInt(st.nextToken());
		int w = Integer.parseInt(st.nextToken());
		edgeQueue.offer(new Edge(u, v, w));
	}
	br.close();

	int result = 0;
	int selectedEdgeCount = 0;

	while (selectedEdgeCount < nodeCount - 2) {
		Edge edge = edgeQueue.poll();
		if (union(edge.u, edge.v, parents)) {
			result += edge.w;
			selectedEdgeCount++;
		}
	}

	bw.write(result + "\n");
	bw.flush();
	bw.close();
}

private static int find(int x, int[] parents) {
	if (parents[x] == x) {
		return x;
	}
	return parents[x] = find(parents[x], parents);
}

private static boolean union(int a, int b, int[] parents) {
	int rootA = find(a, parents);
	int rootB = find(b, parents);
	if (rootA != rootB) {
		parents[rootB] = rootA;
		return true;
	}
	return false;
}

출처:https://www.acmicpc.net/problem/1647