kruskal algorithm implementation for uva freckles problem

freckles.cpp

//
// Created by alice on 27/05/19.
// g++ freckles_10034.cpp -o freckles.o
// uva - 10034 accepted
//

#include <bits/stdc++.h>

using namespace std;

class UnionSet {

public:
    UnionSet (int n_) {
        n = n_;
        for (int i = 0; i < n; ++i) {
            parent.push_back(i);
            size.push_back(1);
        }
    }

    int find_component(int k) {
        return parent[k] == k ? k : find_component(parent[k]);
    }

    void merge(int x, int y) {
        auto parent_x = find_component(x);
        auto parent_y = find_component(y);
        if (parent_x == parent_y) return;
        if (size[parent_x] > size[parent_y]) {
            size[parent_x] += size[parent_y];
            parent[parent_y] = parent_x;
        } else {
            size[parent_y] += size[parent_x];
            parent[parent_x] = parent_y;
        }
    }

    bool same_component(int x, int y) {
        return find_component(x) == find_component(y);
    }

private:
    int n;
    vector<int> parent;
    vector<int> size;
};

double dist(const vector<pair<double, double>>& points, int x, int y) {
    auto a = points[x], b = points[y];
    return sqrt(pow((a.first - b.first), 2) + pow((a.second - b.second), 2));
}

double get_line(const vector<pair<double, double>>& points) {
    vector<tuple<double, int, int>> edges;
    for (int i = 0; i < points.size(); ++i) {
        for (int j = i + 1; j < points.size(); ++j) {
            edges.push_back({dist(points, i, j), i, j});
        }
    }
    sort(edges.begin(), edges.end());

    auto union_set = UnionSet(points.size());

    double edge;
    int p, q;
    double line = 0.0;
    for (int i = 0; i < edges.size(); ++i) {
        tie(edge, p, q) = edges[i];
        if (!union_set.same_component(p, q)) {
            line += edge;
            union_set.merge(p, q);
        }
    }
    return line;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(2) << fixed;
    int t, n;
    cin >> t;
    double x, y, ans;
    for (int i = 0; i < t; ++i) {
        cin >> n;
        vector<pair<double, double>> points;
        for (int j = 0; j < n; ++j) {
            cin >> x >> y;
            points.push_back({x, y});
        }
        ans = get_line(points);
        if (i) cout << endl;
        cout << ans << endl;
    }
    return 0;
}