graph/kruskal.hpp

View this file on GitHub
Last update: 2025-05-09 08:40:27+00:00
Include: #include "graph/kruskal.hpp"

Depends on

Verified with

verify/aizu-GRL_2_A.test.cpp

Code

#pragma once
#include "graphtemplate"
#include "UnionFind"
#include<bits/stdc++.h>
using namespace std;
// クラスカル法を用いて最小全域木を求める O(m log m)
template<class T = int, bool directed = false, bool weighted = true>
graph<T, directed, weighted> kruskal(graph<T, directed, weighted>& g) {
    graph<T, directed, weighted> re(g.size());
    edges<T> _edges = g._edges;
    sort(_edges.begin(), _edges.end(), [](edge<T> e1, edge<T> e2) { return e1.cost < e2.cost;} );
    UnionFind uf(g.size());
    for (auto& _e : _edges) {
        if (uf.merge(_e.from, _e.to)) {
            re.add_edge(_e);
        }
    }
    return re;
}

#line 2 "graph/graphtemplate.hpp"
#include<bits/stdc++.h>
using namespace std;
// 辺の構造体 edge(from, to, cost, id)
template<class T = int>
struct edge {
    int from, to;
    T cost;
    int id;
};
// 頂点の構造体 vector<edge<T>>
template<class T = int>
using edges = vector<edge<T>>;
// グラフの構造体 graph<T, directed, weighted> 
template <class T = int, bool directed = false, bool weighted = false>
struct graph {
    bool isdirected, isweighted;
    edges<T> _edges;
    vector<edges<T>> data;
    T sumcost;
    graph() = default;
    // 頂点数 n のグラフを作成する
    graph(int n) : isdirected(directed), isweighted(weighted), data(n), sumcost(T{}) {}
    // from から to へ辺を追加する
    void add_edge(int from, int to, T cost = 1, int id = -1) {
        if (id == -1) id = _edges.size();
        data[from].push_back(edge<T>(from, to, cost, id));
        _edges.push_back(edge<T>(from, to, cost, id));
        if (!isdirected) {
            data[to].push_back(edge<T>(to, from, cost, id));
        }
        sumcost += cost;
    }
    // 辺を追加する
    void add_edge(edge<T> _e) {
        add_edge(_e.from, _e.to, _e.cost, _e.id);
    }
    // 標準入力から辺を読み込む
    void read(int m, int indexed = 1) {
        for (int i=0; i<m; i++) {
            int from, to;
            T cost = 1;
            cin >> from >> to;
            if (isweighted) cin >> cost;
            add_edge(from - indexed, to - indexed, cost);
        }
    }
    // 頂点数を返す
    int size() {
        return data.size();
    }
    // 頂点を返す
    edges<T> operator[](int k) {
        return data[k];
    }
    vector<int> path_to_vertex(edges<T>& _e) {
        vector<int> re;
        if (_e.size() == 0) {
            return re;
        }
        if (_e.size() == 1) {
            re.push_back(_e[0].from);
            re.push_back(_e[0].to);
            return re;
        }
        int x=_e[0].from,y=_e[0].to;
        if (x==_e[1].to || x == _e[1].from) swap(x, y);
        re.push_back(x);
        for (int i=1; i<_e.size(); i++) {
            re.push_back(y);
            x = _e[i].to;
            if (x == y) x = _e[i].from;
            swap(x, y);
        }
        return re;
    }
    edges<T> vetex_to_path (vector<int>& v){
        edges<T> re;
        for (int i=0; i+1<v.size(); i++) {
            for (auto& _e : this[v[i]]) {
                if (_e.to == v[i+1]) {
                    re.push_back(_e);
                    break;
                }
            }
        }
        return re;
    }
};
#line 3 "structure/UnionFind.hpp"
using namespace std;
struct UnionFind {
    int _n;
    vector<int> data;
    // n 個の要素からなるUnionFind を構築 O(n)
    UnionFind(int n) : _n(n), data(n, -1) {}
    // 2 つの要素を併合 O(α(n))
    bool merge(int p, int q) {
        p = root(p);
        q = root(q);
        if (p == q) return false;
        if (q < p) swap(p, q);
        data[p] += data[q];
        data[q] = p;
        return true;
    }
    // 親要素を取得 O(α(n))
    int root(int p) {
        assert(0 <= p && p < _n);
        if (data[p] < 0) {
            return p;
        } else {
            data[p] = root(data[p]);
            return data[p];
        }
    }
    // 親要素を取得 O(α(n))
    int operator[](int p) {
        return root(p);
    }
    // 2 つの要素が同じ集合に含まれるか判定 O(α(n))
    bool same(int p, int q) {
        return root(p) == root(q);
    }
    // 要素が属する集合の大きさを返す O(α(n))
    int size(int p) {
        return -data[root(p)];
    }
    // UnionFind の連結成分のvector を返す O(n α(n))
    vector<vector<int>> groups() {
        vector<vector<int>> re(_n);
        for (int i=0; i<_n; i++) re[root(i)].push_back(i);
        re.erase(remove_if(re.begin(), re.end(), [](vector<int>& v){ return v.empty(); }), re.end());
        return re;
    }
};
#line 5 "graph/kruskal.hpp"
using namespace std;
// クラスカル法を用いて最小全域木を求める O(m log m)
template<class T = int, bool directed = false, bool weighted = true>
graph<T, directed, weighted> kruskal(graph<T, directed, weighted>& g) {
    graph<T, directed, weighted> re(g.size());
    edges<T> _edges = g._edges;
    sort(_edges.begin(), _edges.end(), [](edge<T> e1, edge<T> e2) { return e1.cost < e2.cost;} );
    UnionFind uf(g.size());
    for (auto& _e : _edges) {
        if (uf.merge(_e.from, _e.to)) {
            re.add_edge(_e);
        }
    }
    return re;
}