3.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 {

// 노드의 개수와 간선의 개수
publicstaticintn, m;
publicstaticint[] parent = newint[200001]; // 부모 테이블 초기화하기
// 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
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);

n = sc.nextInt();
m = sc.nextInt();

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

// 모든 간선에 대한 정보를 입력 받기
for (inti = 0; i < m; i++) {
intx = sc.nextInt();
inty = sc.nextInt();
intz = sc.nextInt();
edges.add(newEdge(z, x, y));
 }

// 간선을 비용순으로 정렬
Collections.sort(edges);
inttotal = 0; // 전체 가로등 비용

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

System.out.println(total - result);
 }
}