[알고리즘] SW expert - 최소 스패닝 트리 java (크루스칼 풀이)

import java.util.*;
import java.io.*;

public class swea최소스패닝트리_크루스칼버전 {
	
	static class Edge implements Comparable<Edge>{
		int from;
		int to; 
		int weight;
		
		Edge(int from, int to, int weight){
			this.from = from;
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return this.weight-o.weight;
		}
	}
	
	static int nodenum ;
	static int edgenum ;
	
	static int[] v_parent;
	
	static void makeset() {
		for(int i=1; i<=nodenum; i++) {
			v_parent[i]=i;
		}
	}
	
	static void unionset(int node1, int node2) {
		
		int node1p = findset(node1);
		int node2p = findset(node2);
		
		if(node1p>node2p)v_parent[node2p]=node1p;
		else v_parent[node1p]=node2p;
	}
	
	static int findset(int nodenum) {
		
		if(v_parent[nodenum]==nodenum)return nodenum;
		else return v_parent[nodenum] = findset(v_parent[nodenum]);
	}
	
	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int tc = Integer.parseInt(br.readLine());		//tc입력
		
		for(int t=1; t<=tc; t++) {						
			StringTokenizer ST = new StringTokenizer(br.readLine());
			
			nodenum = Integer.parseInt(ST.nextToken());
			edgenum = Integer.parseInt(ST.nextToken());
			PriorityQueue<Edge> pq = new PriorityQueue<>();		//간선정보 넣을 pq
			
			for(int k=0; k<edgenum; k++) {
				ST = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(ST.nextToken());
				int to = Integer.parseInt(ST.nextToken());
				int weight = Integer.parseInt(ST.nextToken());
				
				pq.add(new Edge(from,to,weight));
			}
			
			v_parent = new int[nodenum+1];	//node번호 1부터니까 +1로 선언 
			makeset();						//자기 자신으로 부모 셋팅 
			
			long result = 0;
			int setnum = 1;
			for(int i=0; i<edgenum; i++) {	//pq에서 하나씩 꺼내면서 union만들기 
				Edge now = pq.poll();
				int nowfrom = now.from;
				int nowto = now.to;
				int nowweight = now.weight;
				
				if(findset(nowfrom)==findset(nowto))continue;
				else {
					unionset(nowfrom, nowto);
					result+=nowweight;
					setnum++;
					//System.out.println("from:"+nowfrom+" to:"+nowto+" weight:"+nowweight);
				}
				//System.out.println(Arrays.toString(v_parent));
				if(setnum==nodenum)break;
			}
			
			System.out.println("#"+t+" "+result);
		}
		
		
	}
}