[デコード]クルーズアルゴリズム

// N은 노드의 개수이다.
void make() {
	parents = new int[N];
    for ( int i = 0 ; i<N ; i++ ) {
    	parents[i];
}

int find(int a){
	if ( a == parents[a] ) return a;
	return parents[a] = find(parents[a]);
}

boolean union(int a, int b){
	int a_root = find(a);
    int b_root = find(b);
    if ( a_root == b_root ) return false; 
    parents[b_root] = a_root;
    return true;
}

public class Solution {
	static class Node implements Comparable<Node> {
		int a;
		int b;
		int cost;
		public Node(int a, int b, int cost) {
			this.a = a;
			this.b = b;
			this.cost = cost;
		}
		@Override
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}
		
	}
	static int N;
	// 우선순위 큐로 구현해도 된다.
	static PriorityQueue<Node> road;
	static int[] parents;
	// 소속 찾기
	static int find(int param ) {
		if ( param == parents[param]) return param;
		return parents[param] = find(parents[param]);
	}
	static boolean union(int A, int B) {
		int A_union = find(A);
		int B_union = find(B);
		if ( A_union == B_union ) {
			return false;
			// 같은 집합이다.
		}
		parents[B_union] = A_union;
		return true;
	}
	
	
	static public int solution(int n, int[][] costs) {
		// 초기화
		int answer = 0;
		N = n;
		parents = new int[n];
		// 모든 원소를 자신의 대표자로
		for (int i = 0; i < N; i++) {
			parents[i] = i;
		}
		Arrays.sort(costs, (e1,e2) -> e1[2] - e2[2]);
		int temp = 0;
		for(int[] arr : costs) {
        
			int a = arr[0];
			int b = arr[1];
			int cost = arr[2];
			
			if ( union(arr[0], arr[1] )) {
				answer += arr[2];
				temp += 1;
				if ( temp >= N ) break;
			}
			if ( temp >= n ) break;
		}
        return answer;
    }
}