백준 1197번 최소 스패닝 트리 C++

출처 : https://www.acmicpc.net/problem/1197

 

유니온 파인드와 크루스칼 알고리즘을 이용해서 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

struct RouteCost {
	int start;
	int end;
	int cost;
	bool operator<(RouteCost& other) {
		return cost < other.cost;
	}
};

vector<int> parent;
vector<int> height;
vector<RouteCost> routes;

int GetParent(int n) {

	if (n == parent[n])
		return n;

	parent[n] = GetParent(parent[n]);
	return parent[n];
}

void Merge(int u, int v) {

	u = GetParent(u);
	v = GetParent(v);

	if (u == v)
		return;

	if (height[u] > height[v])
		swap(u, v);

	parent[u] = v;

	if (height[u] == height[v])
		height[v]++;
}

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

	int v, e;
	cin >> v >> e;
	parent = vector<int>(v + 1);
	height = vector<int>(v + 1, 1);
	for (int i = 1; i <= v; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < e; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		routes.push_back({ start,end,cost });
	}
	sort(routes.begin(), routes.end());
	int64 sum = 0;
	for (int i = 0; i < e; i++) {
		int start = routes[i].start;
		int end = routes[i].end;
		int64 cost = routes[i].cost;

		if (GetParent(start) == GetParent(end))
			continue;

		sum += cost;
		Merge(start, end);
	}
	cout << sum;
}