백준 #1922 네트워크 연결 : 최소신장트리(MST)

https://www.acmicpc.net/problem/1922

최소 신장 트리 (MST) 구하는 알고리즘

1. 프림

2. 크루스칼

​

크루스칼 알고리즘과 유니온파인드 자료구조를 활용해서 해결

 

#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;

int N, M;

priority_queue<tuple<int, int, int>> q;
int uf[100001];

int Find(int x) {
	if (x == uf[x]) return x;
	
	int p = Find(uf[x]);
	uf[x] = p;
	return p;
}

bool Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	if (x != y) {
		uf[y] = x;
		return true;
	}
	return false;
}

int main(int argc, char argv[]) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
		uf[i] = i;

	for (int i = 0; i < M; i++) {
		int h1, h2, c;
		cin >> h1 >> h2 >> c;
		q.push({ -c, h1, h2 });
	}
	int cost_sum = 0;
	int count = 0;

	while (!q.empty()) {
		if (count == N - 1) break;
		int h1, h2, c;
		c = -get<0>(q.top());
		h1 = get<1>(q.top());
		h2 = get<2>(q.top());
		q.pop();
		if (Union(h1, h2)) {
			cost_sum += c;
			count++;
		}
	}
	cout << cost_sum;
}