[백준] 1197. 최소 스패닝 트리 (크루스칼 알고리즘, MST)

 

www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

import java.util.PriorityQueue;
import java.util.Scanner;

class edge implements Comparable<edge>{
	int s;
	int e;
	int w;

	public edge(int s, int e, int w) {
		super();
		this.s = s;
		this.e = e;
		this.w = w;
	}

	@Override
	public int compareTo(edge o) {
		return this.w-o.w;
	}
	
}

public class Main {
	static int v,e;
	static int[] parent;
	static PriorityQueue<edge> pq=new PriorityQueue<>();
	static int result=0;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		v=sc.nextInt();
		e=sc.nextInt();
		parent=new int[v+1];
		for (int i = 1; i <= v; i++) {
			parent[i]=i;
		}
		for (int i = 0; i < e; i++) {
			pq.add(new edge(sc.nextInt(),sc.nextInt(),sc.nextInt()));
		}
		
		for (int i = 0; i < e; i++) {
			edge a=pq.poll(); // 간선의 가중치 낮은 순으로 합침
			union(a.s,a.e,a.w);
		}
		System.out.println(result);
	}
	private static int find(int x) {
		if(x==parent[x])return x;
		return parent[x]=find(parent[x]);
	}
	
	private static void union(int x,int y,int w) {
		x=find(x);
		y=find(y);
		if(x!=y) {//사이클이 아닌 경우만 union
			parent[x]=y;
			result+=w;
		}
	}
}