백준 1774번 : 우주신과의 교감 - 크루스칼 MST C++

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

1774번: 우주신과의 교감

#include <bits/stdc++.h>
using namespace std;

int unf[1001];

int Find(int x) {
	if (x == unf[x]) {
		return x;
	}
	else return unf[x] = Find(unf[x]);
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if (a != b) {
		unf[a] = b;
	}
}

struct Edge {
	int x, y;
	double val;
	bool operator<(const Edge& b)const {
		return val > b.val;
	}
};

double distance(int x1, int y1, int x2, int y2) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	priority_queue<Edge> Q;
	for (int i = 0; i < 1001; i++) {
		unf[i] = i;
	}

	vector<pair<int,int> > v;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a, b });
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		Union(a-1, b-1);
	}


	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			double dist = distance(v[i].first, v[i].second, v[j].first, v[j].second);
			Q.push({ i,j,dist });
		}
	}

	double ans = 0;

	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		double val = Q.top().val;
		Q.pop();

		if (Find(x) != Find(y)) {
			Union(x, y);
			ans += val;
		}
	}

	cout << fixed;
	cout.precision(2);
	cout << ans << '\n';

	return 0;
}

백준 1774번