<aside> 💛

시간 제한 : 2초, 난이도 : 골드 4, 백준 : 1197번

</aside>

최소 신장 트리는 주어진 그래프의 모든 노드들을 연결하는 부분 그래프 중 그 가중치의 합이 최소인 트리를 말한다.

import java.util.PriorityQueue;
import java.util.Scanner;
public class Practice64 {
	static int[] parent;
	static PriorityQueue<Edge> queue;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		queue = new PriorityQueue<>();
		parent = new int[N + 1];
	
		for(int i = 0; i < N; i++) {
			parent[i] = i;
		}
		for(int i = 0; i < M; i++) {
			int s = sc.nextInt();
			int e = sc.nextInt();
			int v = sc.nextInt();
			queue.add(new Edge(s, e, v));
		}
		int useEdge = 0;
		int result = 0;
		while(useEdge < N - 1) {
			Edge now = queue.poll();
			if(find(now.s) != find(now.e)) {
				union(now.s, now.e);
				result = result + now.v;
				useEdge++;
			}
		}
		System.out.println(result);		

	}
	public static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
	}
	public static int find(int a) {
		if(a == parent[a])
			return a;
		else
			return parent[a] = find(parent[a]);		
	}

}

class Edge implements Comparable<Edge>{
	int s;
	int e;
	int v;
	Edge(int s, int e, int v){
		this.s = s;
		this.e = e;
		this.v = v;
	}
	@Override
	public int compareTo(Edge o) { //오름차순 정렬 위함
		return this.v - o.v;
	}
}