// 위의 그림처럼 그래프가 주어졌을 때

class DisjointSet {
	constructor(n) {
		this.parent = Array.from({length: n}, (_, i) => i); //init (편의상 i)
		this.rank = Array.from({length: n}, () => 1);
	}

	// u가 속한 트리의 루트의 번호를 반환
	find(u) {
		if (u === this.parent[u]) return u;
		return (this.parent[u] = this.find(this.parent[u]));
	}

	// u가 속한 트리와 v가 속한 트리를 합친다.
	union(u, v) {
		u = this.find(u);
		v = this.find(v);

		// u와 v가 이미 같은 트리에 속하는 경우를 걸러낸다.
		if (u === v) return;
		if (this.rank[u] > this.rank[v]) {
			const temp = u;
			u = v;
			v = temp;
		}
		// 이제 rank[v]가 항상 rank[u] 이상이므로 u를 v의 자식으로 넣는다.
		this.parent[u] = v;
		if (this.rank[u] === this.rank[v]) ++this.rank[v];
	}
}

// 간선 정보를 저장할 객체를 만들 클래스
class Edge {
	constructor(start, end, weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
}

const Kruskal = () => {
	// 결과 배열
	const result = [];

	// 그림에 맞게 그래프 생성 (연결리스트나 인접행렬이 아닌 그저 간선 정보를 가지고 있는 배열)
	const graph = [];
	graph.push(new Edge(0, 1, 14));
	graph.push(new Edge(0, 2, 12));
	graph.push(new Edge(0, 3, 45));
	graph.push(new Edge(1, 2, 28));
	graph.push(new Edge(1, 3, 9));
	graph.push(new Edge(1, 4, 63));
	graph.push(new Edge(2, 3, 32));
	graph.push(new Edge(3, 4, 51));

	// union-find 자료구조 생성 (총 정점의 개수는 5개)
	const set = new DisjointSet(5);

	// 가중치 기준으로 오름차순 정렬
	graph.sort((a, b) => a.weight - b.weight);

	// 예를 들어, MST의 가중치의 합
	let sum = 0;
	for (let i = 0; i < graph.length; i++) {
		const {start, end, weight} = graph[i];

		// 만약 둘이 같은 컴포넌트에 있으면 (추가시 사이클 생김)
		if (set.find(start) === set.find(end)) continue;

		set.union(start, end);
		result.push([start, end, weight]);
		sum += weight;
	}

	console.log(sum); // 86
	console.log(result); // [[ 1, 3, 9 ], [ 0, 2, 12 ], [ 0, 1, 14 ], [ 3, 4, 51 ]]
};

Kruskal();