kruskal algorithm implementation

kruskal.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

class Edge
{
public:
    Edge(int s, int d, int w) :
        m_s(s), m_d(d), m_w(w)
    {}

    inline const int get_s() const { return m_s; }  ///< source
    inline const int get_d() const { return m_d; }  ///< destination
    inline const int get_w() const { return m_w; }  ///< weight

private:
    int m_s, m_d, m_w;
};

std::ostream& operator<<(std::ostream& os, const std::vector<Edge>& E)
{
    int total_w = 0;
    os << "Edges [source / destination / weight]\n";
    for (const Edge& e : E)
    {
        os << e.get_s() << " / " << e.get_d() << " / " << e.get_w() << "\n";
        total_w += e.get_w();
    }
    os << "Total cost: " << total_w << "\n";
    return os;
}

std::vector<Edge> kruskal(std::vector<Edge>& g)
{
    using subsets_t = std::vector<std::pair<std::size_t, std::size_t>>;

    subsets_t subsets(g.size());
    for (std::size_t i = 0; i < g.size(); ++i)
        subsets[i] = std::make_pair(i, 0);

    std::sort(g.begin(), g.end(), [](const Edge& lhs, const Edge& rhs) -> bool {
        return lhs.get_w() < rhs.get_w();
    });

    std::function<std::size_t(std::size_t, subsets_t&)> find = [&find](std::size_t i, subsets_t& sub) -> std::size_t {
        if (sub[i].first != i)
            sub[i].first = find(sub[i].first, sub);
        return sub[i].first;
    };

    std::vector<Edge> min_span_tree;

    for (const Edge& current : g)
    {
        std::size_t x = find(current.get_s(), subsets),
                    y = find(current.get_d(), subsets);

        if (x != y)
        {
            min_span_tree.push_back(current);
            std::size_t x_root = find(x, subsets),
                        y_root = find(y, subsets);

            if (std::size_t& snd = subsets[x_root].second; snd < subsets[y_root].second)
                subsets[x_root].first = y_root;
            else if (snd > subsets[y_root].second)
                subsets[y_root].first = x_root;
            else
            {
                subsets[x_root].first = y_root;
                subsets[y_root].second++;
            }
        }
    }

    return min_span_tree;
}

int main()
{
    std::vector<Edge> g;
    g.emplace_back(0, 1, 50);
    g.emplace_back(0, 2, 10);
    g.emplace_back(0, 3, 50);
    g.emplace_back(1, 4, 30);
    g.emplace_back(3, 4, 100);
    g.emplace_back(2, 4, 100);

    std::cout << kruskal(g) << std::endl;

    return 0;
}