백준 1774번 우주신과의 교감 C++

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

1774번: 우주신과의 교감

 

유니온 파인드 자료구조를 이용해서 최소 스패닝 트리로 풀었다.

 

#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;

int n, m;

vector<int> parent;
vector<int> height;
vector<pair<int64, int64>> v;
vector<pair<double, pair<int64, int64>>> dists;

double GetDist(pair<int64, int64>& loc1, pair<int64, int64>& loc2) {
    return sqrt(pow(loc2.first - loc1.first, 2) + pow(loc2.second - loc1.second, 2));
}

int GetParent(int a) {
    if (a == parent[a]) return a;
    return parent[a] = GetParent(parent[a]);
}

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);

    cin >> n >> m;
    parent = vector<int>(n + 1);
    height = vector<int>(n + 1, 1);
    for (int i = 1; i <= n; i++) parent[i] = i;
    v.push_back({ 0,0 });
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back({ x,y });
    }
    double ans = 0;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        Merge(x, y);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            dists.push_back({ GetDist(v[i],v[j]),{i,j} });
        }
    }
    sort(dists.begin(), dists.end());
    for (auto a : dists) {
        int x = a.second.first;
        int y = a.second.second;
        if (GetParent(x) == GetParent(y)) continue;
        Merge(x, y);
        ans += a.first;
    }
    cout << fixed;
    cout.precision(2);
    cout << ans;
}