5.java

importjava.util.*;

classEdgeimplementsComparable<Edge> {

privateintdistance;
privateintnodeA;
privateintnodeB;

publicEdge(intdistance, intnodeA, intnodeB) {
this.distance = distance;
this.nodeA = nodeA;
this.nodeB = nodeB;
 }

publicintgetDistance() {
returnthis.distance;
 }

publicintgetNodeA() {
returnthis.nodeA;
 }

publicintgetNodeB() {
returnthis.nodeB;
 }

// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
@Override
publicintcompareTo(Edgeother) {
if (this.distance < other.distance) {
return -1;
 }
return1;
 }
}

publicclassMain {

// 노드의 개수(V)와 간선(Union 연산)의 개수(E)
// 노드의 개수는 최대 100,000개라고 가정
publicstaticintv, e;
publicstaticint[] parent = newint[100001]; // 부모 테이블 초기화하기
// 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
publicstaticArrayList<Edge> edges = newArrayList<>();
publicstaticintresult = 0;

// 특정 원소가 속한 집합을 찾기
publicstaticintfindParent(intx) {
// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
if (x == parent[x]) returnx;
returnparent[x] = findParent(parent[x]);
 }

// 두 원소가 속한 집합을 합치기
publicstaticvoidunionParent(inta, intb) {
a = findParent(a);
b = findParent(b);
if (a < b) parent[b] = a;
elseparent[a] = b;
 }

publicstaticvoidmain(String[] args) {
Scannersc = newScanner(System.in);

v = sc.nextInt();
e = sc.nextInt();

// 부모 테이블상에서, 부모를 자기 자신으로 초기화
for (inti = 1; i <= v; i++) {
parent[i] = i;
 }

// 모든 간선에 대한 정보를 입력 받기
for (inti = 0; i < e; i++) {
inta = sc.nextInt();
intb = sc.nextInt();
intcost = sc.nextInt();
edges.add(newEdge(cost, a, b));
 }

// 간선을 비용순으로 정렬
Collections.sort(edges);

// 간선을 하나씩 확인하며
for (inti = 0; i < edges.size(); i++) {
intcost = edges.get(i).getDistance();
inta = edges.get(i).getNodeA();
intb = edges.get(i).getNodeB();
// 사이클이 발생하지 않는 경우에만 집합에 포함
if (findParent(a) != findParent(b)) {
unionParent(a, b);
result += cost;
 }
 }

System.out.println(result);
 }
}