test/AOJ/GRL_2_A-Minimum-Spanning-Tree.test.cpp

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp"
#include <iostream>

#include "../../Graph/graph-template.hpp"
#include "../../Graph/Minimum-Spanning-Tree/kruskal.hpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int V, E;
    std::cin >> V >> E;

    std::vector<Edge<int>> es(E);
    for (int i = 0; i < E; ++i) {
        std::cin >> es[i];
    }

    std::cout << kruskal<int>(V, es) << std::endl;

    return 0;
}

#line 1 "test/AOJ/GRL_2_A-Minimum-Spanning-Tree.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_A&lang=jp"
#include <iostream>

#line 2 "Graph/graph-template.hpp"
#include <cstdint>
#include <vector>
#line 5 "Graph/graph-template.hpp"

/**
 * @brief graph-template (Edge, Graph, MatrixGraph)
 */
//! グラフの辺 (重み付き)
template <class T>
struct Edge {
    int from, to;
    T weight;
    int id;

    Edge() = default;

    constexpr explicit Edge(int to_, const T& weight_)
        : Edge(-1, to_, weight_, -1) {}

    constexpr Edge(int from_, int to_, const T& weight_, int id_ = -1)
        : from(from_)
        , to(to_)
        , weight(weight_)
        , id(id_) {}

    constexpr const Edge rev() const { return Edge(to, from, weight, id); }

    template <class Int, std::enable_if_t<std::is_integral<Int>::value, std::nullptr_t> = nullptr>
    constexpr operator Int() const {
        return static_cast<Int>(to);
    }

    friend std::istream& operator>>(std::istream& is, Edge& e) { return is >> e.from >> e.to >> e.weight; }
};

//! グラフの辺 (重みなし)
template <>
struct Edge<void> {
    int from, to;
    int id;

    Edge() = default;

    constexpr explicit Edge(int to_)
        : Edge(-1, to_, -1) {}

    constexpr Edge(int from_, int to_, int id_ = -1)
        : from(from_)
        , to(to_)
        , id(id_) {}

    constexpr const Edge rev() const { return Edge(to, from, id); }

    template <class Int, std::enable_if_t<std::is_integral<Int>::value, std::nullptr_t> = nullptr>
    constexpr operator Int() const {
        return static_cast<Int>(to);
    }

    friend std::istream& operator>>(std::istream& is, Edge& e) { return is >> e.from >> e.to; }
};

template <class T>
using Graph = std::vector<std::vector<Edge<T>>>;
#line 2 "Graph/Minimum-Spanning-Tree/kruskal.hpp"
#include <algorithm>
#line 4 "Graph/Minimum-Spanning-Tree/kruskal.hpp"

#line 2 "Data-Structure/Disjoint-Set/union-find.hpp"
#include <cassert>
#line 5 "Data-Structure/Disjoint-Set/union-find.hpp"
#include <utility>
#line 7 "Data-Structure/Disjoint-Set/union-find.hpp"

/**
 * @brief Union-Find (素集合データ構造)
 * @note path-compression + union-by-size
 */
class UnionFind {
private:
    int n;
    mutable std::vector<int> p;

public:
    UnionFind() = default;

    explicit UnionFind(int n_)
        : n(n_)
        , p(n_, -1) {}

    int unite(int x, int y) {
        x = leader(x), y = leader(y);
        if (x == y) return x;
        if (p[y] < p[x]) std::swap(x, y);
        p[x] += p[y];
        p[y] = x;
        return x;
    }

    int leader(int x) const { return p[x] < 0 ? x : p[x] = leader(p[x]); }

    bool same(int x, int y) const { return leader(x) == leader(y); }

    int size(int x) const { return -p[leader(x)]; }

    std::vector<std::vector<int>> groups() const {
        std::vector<int> leaderBuf(n), groupSize(n);
        for (int i = 0; i < n; i++) ++groupSize[leaderBuf[i] = leader(i)];

        std::vector<std::vector<int>> result(n);
        for (int i = 0; i < n; i++) result[i].reserve(groupSize[i]);
        for (int i = 0; i < n; i++) result[leaderBuf[i]].push_back(i);
        result.erase(std::remove_if(result.begin(), result.end(), [](const std::vector<int>& v) { return v.empty(); }), result.end());
        return result;
    }
};
#line 7 "Graph/Minimum-Spanning-Tree/kruskal.hpp"

/**
 * @brief kruskal() (クラスカル法)
 */
template <class ResultType, class WeightType>
ResultType kruskal(int V, std::vector<Edge<WeightType>>& edges) {
    ResultType weightSum{};
    UnionFind uf(V);
    std::sort(edges.begin(), edges.end(), [](const auto& e1, const auto& e2) {
        return e1.weight < e2.weight;
    });
    for (const auto &e : edges) {
        if (uf.same(e.from, e.to)) continue;
        uf.unite(e.from, e.to);
        weightSum += e.weight;
    }
    return weightSum;
}
#line 6 "test/AOJ/GRL_2_A-Minimum-Spanning-Tree.test.cpp"

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    int V, E;
    std::cin >> V >> E;

    std::vector<Edge<int>> es(E);
    for (int i = 0; i < E; ++i) {
        std::cin >> es[i];
    }

    std::cout << kruskal<int>(V, es) << std::endl;

    return 0;
}