백준 1647번 : 도시 분할 계획

문제 링크 : www.acmicpc.net/problem/1647

내 풀이(2021.2.6.) : 최소 신장 트리

#include <iostream>
#include <queue>
#include <tuple>

using namespace std;

typedef tuple<int, int, int> tp;

priority_queue<tp, vector<tp>, greater<tp>> pq;
int p[100001];

int find(int n) {
	if (p[n] != n) p[n] = find(p[n]);
	return p[n];
}

void union_(int a, int b) {
	a = find(a); b = find(b);
	if (a < b) p[b] = a;
	else p[a] = b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M; cin >> N >> M;
	
	for (int i = 1; i <= N; i++) {
		p[i] = i;
	}

	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
		pq.push(make_tuple(c, a, b));
	}

	int total = 0;
	int last = 0;
	for (int i = 0; i < M; i++) {
		tp t = pq.top(); pq.pop();
		int cost = get<0>(t);
		int a = get<1>(t);
		int b = get<2>(t);

		if (find(a) == find(b)) continue;
		union_(a, b);
		total += cost;
		last = cost;
	}

	cout << total - last;

	return 0;
}