题解 | #【模板】最小生成树#

Kruskal克鲁斯卡尔算法模板题

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

const ll N = 5e5 + 5, mod = 1e9 + 7, inf = 2e18;
const double esp = 1e-8;

int n, m, fa[N];
vector<int>res;

struct Node {
    ll u, v, w, id;
    bool operator<(const Node& a)const {
        return w < a.w;
    }
} g[N];

int find(int x) {
    if (x == fa[x])return x;

    return fa[x] = find(fa[x]);
}

void me(int x, int y) {
    fa[x] = find(x);

    fa[fa[x]] = find(y);
}

void Kruskal() {
    ll cont = 0, ans = 0;

    for (int i = 1; i <= m; i++) {
        auto [u, v, w, id] = g[i];

        if (find(u) == find(v))continue;

        res.push_back(id);
        ans += w;
        cont++;

        me(u, v);

        if (cont == n - 1) {
            cout << ans << '\n';

            for (auto i : res) {
                cout << i << " ";
            }
            return ;
        }
    }
}


void solve() {
    cin >> n >> m;

    iota(fa, fa + n + 4, 0);

    for (int i = 1; i <= m; i++) {
        auto &[u, v, w, id] = g[i];

        cin >> u >> v >> w;
        id = i;
    }

    sort(g + 1, g + 1 + m);

    Kruskal();
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}