test/yosupo/graph/minimum_spanning_tree_kruskal.test.cpp

• View this file on GitHub
• Last update: 2025-09-20 17:47:50+07:00
• Problem: https://judge.yosupo.jp/problem/minimum_spanning_tree

Depends on

• Disjoint Set Union (graph/dsu.hpp)
• other/types.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/minimum_spanning_tree"

#include <bits/stdc++.h>
using namespace std;

#include "graph/dsu.hpp"
#include "other/types.hpp"

i32 main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    struct Edge {
        i32 u, v;
        i64 w;
    };
    i32 n, m;
    cin >> n >> m;

    vector<Edge> es(m);
    vector<i32> id(m);
    iota(begin(id), end(id), 0);

    for (auto &[u, v, w] : es) cin >> u >> v >> w;
    sort(begin(id), end(id), [&](i32 i, i32 j) { return es[i].w < es[j].w; });
    DSU dsu(n);

    i64 cost = 0;
    vector<i32> mst;
    for (int i : id) {
        if (dsu.merge(es[i].u, es[i].v)) {
            cost += es[i].w;
            mst.push_back(i);
        }
    }
    cout << cost << "\n";
    for (int i = 0; i < n - 1; i++) cout << mst[i] << " \n"[i == n - 2];
}

#line 1 "test/yosupo/graph/minimum_spanning_tree_kruskal.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/minimum_spanning_tree"

#include <bits/stdc++.h>
using namespace std;

#line 2 "graph/dsu.hpp"

struct DSU {
    vector<int> data;
    DSU() : DSU(0) {}
    DSU(int n) : data(n, -1) {}

    void reset(int n) {
        if (data.size() < n) data.resize(n);
        fill_n(begin(data), n, -1);
    }
    int size(int x) { return -data[find(x)]; }
    int find(int x) { return data[x] < 0 ? x : data[x] = find(data[x]); }
    bool same(int x, int y) { return find(x) == find(y); }
    bool merge(int x, int y) {
        return merge(x, y, [](auto...) {});
    }
    template<class F> bool merge(int x, int y, F &&f) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += exchange(data[y], x);
        f(x, y);
        return true;
    }
};
#line 2 "other/types.hpp"

using i8 = int8_t;
using u8 = uint8_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
using f80 = long double;
using str = string;
template<class T> using vec = vector<T>;
template<class E = i32> using graph = vec<vec<E>>;
#line 8 "test/yosupo/graph/minimum_spanning_tree_kruskal.test.cpp"

i32 main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    struct Edge {
        i32 u, v;
        i64 w;
    };
    i32 n, m;
    cin >> n >> m;

    vector<Edge> es(m);
    vector<i32> id(m);
    iota(begin(id), end(id), 0);

    for (auto &[u, v, w] : es) cin >> u >> v >> w;
    sort(begin(id), end(id), [&](i32 i, i32 j) { return es[i].w < es[j].w; });
    DSU dsu(n);

    i64 cost = 0;
    vector<i32> mst;
    for (int i : id) {
        if (dsu.merge(es[i].u, es[i].v)) {
            cost += es[i].w;
            mst.push_back(i);
        }
    }
    cout << cost << "\n";
    for (int i = 0; i < n - 1; i++) cout << mst[i] << " \n"[i == n - 2];
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	4 ms	4 MB
g++	example_01	AC	3 ms	4 MB
g++	example_02	AC	3 ms	4 MB
g++	max_random_00	AC	152 ms	17 MB
g++	max_random_01	AC	153 ms	17 MB
g++	max_random_02	AC	149 ms	17 MB
g++	max_random_03	AC	151 ms	17 MB
g++	max_random_04	AC	148 ms	17 MB
g++	random_00	AC	122 ms	15 MB
g++	random_01	AC	143 ms	17 MB
g++	random_02	AC	106 ms	12 MB
g++	random_03	AC	141 ms	16 MB
g++	random_04	AC	112 ms	14 MB
g++	small_00	AC	93 ms	11 MB
g++	small_01	AC	97 ms	11 MB
g++	small_02	AC	87 ms	11 MB
g++	small_03	AC	10 ms	4 MB
g++	small_04	AC	25 ms	5 MB
g++	small_c01_00	AC	4 ms	4 MB
g++	small_c01_01	AC	4 ms	4 MB
g++	small_c01_02	AC	3 ms	4 MB
g++	small_c01_03	AC	3 ms	4 MB
g++	small_c01_04	AC	3 ms	4 MB
g++	star_00	AC	141 ms	17 MB
clang++	example_00	AC	4 ms	4 MB
clang++	example_01	AC	3 ms	4 MB
clang++	example_02	AC	3 ms	4 MB
clang++	max_random_00	AC	151 ms	17 MB
clang++	max_random_01	AC	150 ms	17 MB
clang++	max_random_02	AC	150 ms	17 MB
clang++	max_random_03	AC	157 ms	17 MB
clang++	max_random_04	AC	155 ms	17 MB
clang++	random_00	AC	123 ms	15 MB
clang++	random_01	AC	150 ms	17 MB
clang++	random_02	AC	111 ms	12 MB
clang++	random_03	AC	143 ms	16 MB
clang++	random_04	AC	115 ms	14 MB
clang++	small_00	AC	95 ms	11 MB
clang++	small_01	AC	98 ms	11 MB
clang++	small_02	AC	87 ms	11 MB
clang++	small_03	AC	10 ms	4 MB
clang++	small_04	AC	25 ms	5 MB
clang++	small_c01_00	AC	5 ms	4 MB
clang++	small_c01_01	AC	4 ms	4 MB
clang++	small_c01_02	AC	4 ms	4 MB
clang++	small_c01_03	AC	3 ms	4 MB
clang++	small_c01_04	AC	3 ms	4 MB
clang++	star_00	AC	144 ms	17 MB

Back to top page