[21924] 도시 건설 C++

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

21924번: 도시 건설

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<pair<int, pair<int, int>>> vec;
int boss[100001];
int visit[100001] = { 0 };

int findBoss(int a) {
	if (boss[a] == a)
		return a;
	else
		return boss[a] = findBoss(boss[a]);
}

void setUnion(int a, int b) {
	a = findBoss(a);
	b = findBoss(b);

	if (a != b)
		boss[b] = a;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	long long sum = 0;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		sum += c;

		vec.push_back(make_pair(c, make_pair(a, b)));
	}

	sort(vec.begin(), vec.end());

	for (int i = 1; i <= N; i++) {
		boss[i] = i;
	}

	long long result = 0;
	for (int i = 0; i < M; i++) {
		int a = vec[i].second.first;
		int b = vec[i].second.second;
		if (findBoss(a) != findBoss(b)) {
			setUnion(a, b);
			visit[a] = 1;
			visit[b] = 1;
			result += vec[i].first;
		}
	}

	for (int i = 1; i < N; i++) {
		if (findBoss(i) != findBoss(i+1)) {
			cout << -1;
			return 0;
		}
	}

	cout << sum - result;

	return 0;
}