[이것이 코딩 테스트다] 도시 분할 계획

❓ 문제 ❓
도시를 2개로 분할 한 후 가장 유지비가 싼 도로만을 남겨 유지비를 구하여라

💯 문제 풀이 💯
크루스칼 알고리즘을 사용해서 최소 신장 트리를 찾은 뒤 가장 비싼 도로를 끊으면 된다!

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int node[100001];

int find_parent(int a) {
	if (node[a] == a) return a;
	else return node[a] = find_parent(node[a]);
}

void union_node(int a, int b) {
	int a_p = find_parent(a);
	int b_p = find_parent(b);
	if (a_p < b_p)
		node[b_p] = a_p;
	else
		node[a_p] = b_p;
}

int main() {
	int n, m;
	priority_queue<pair<int, pair<int, int>>> pq;	// cost, a->b
	vector<int> answer;
	cin >> n >> m;

	for (int i = 1; i <= n; i++)
		node[i] = i;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		pq.push({ -c, {a,b} });
	}
	while (!pq.empty()) {
		int cost = pq.top().first;
		int cur = pq.top().second.first;
		int next = pq.top().second.second;
		pq.pop();
		int a = find_parent(cur);
		int b = find_parent(next);
		if (a != b) {
			union_node(a, b);
			answer.push_back(-cost);
		}
	}
	sort(answer.begin(), answer.end());
	int sum = 0;
	for (int i = 0; i < answer.size() - 1; i++) {
		sum += answer[i];
	}
	cout << sum;
}