[알고리즘] 백준 21924번: 도시 건설 (C++)

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

21924번: 도시 건설

입력받으면서 모든 가중치를 더하고, MST를 구성하는 가중치 값들을 빼준다.

단, MST 간선의 개수 조건에 의해 간선의 개수가 N - 1이 되지 않았다면 -1을 출력한다.

[AC 코드]

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#define MAX (100000 + 1)
#define pii pair<int, int>
#define ll long long
using namespace std;

int n, m;
vector<pair<pii, ll>> edges;
int parent[MAX];

bool cmp(pair<pii, ll> a, pair<pii, ll> b) {
	return a.second < b.second;
}

int getRoot(int node) {
	if (node == parent[node]) {
		return node;
	}
	return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b) {
	int rA = getRoot(a);
	int rB = getRoot(b);

	if (rA != rB) return true;
	else return false;
}

void unionParent(int a, int b) {
	int rA = getRoot(a);
	int rB = getRoot(b);
	if (rA < rB) {
		parent[rB] = rA;
	}
	else parent[rA] = rB;
}

int main() {
	cin >> n >> m;
	ll sum = 0;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edges.push_back({ {a, b}, c });
		sum += c;
	}

	sort(edges.begin(), edges.end(), cmp);

	for (int i = 1; i <= n; i++) {
		parent[i] = i;
	}

	int cnt = 0;
	ll result = 0;
	for (int i = 0; i < edges.size(); i++) {
		int s = edges[i].first.first;
		int e = edges[i].first.second;
		if (find(s, e)) {
			unionParent(s, e);
			cnt++;
			result += edges[i].second;
		}
	}

	if (cnt == n - 1) cout << sum - result;
	else cout << -1;
	return 0;
}