kruskal.cpp

// Author: Sander de Beet

#include <bits/stdc++.h>  // This will work only for g++ compiler.

#define f0r(i, n) for (int i = 0; i < (int)(n); ++i) // 0 based indexing
#define f1r(i, n) for (int i = 1; i <= (int)(n); ++i) // 1 based indexing
#define f0rr(i, n) for (int i = (int)(n) - 1; i >= 0; --i) // reverse 0 based.
#define f1rr(i, n) for (int i = (int)(n); i >= 1; --i) // reverse 1 based

// short hand for usual tokens
#define pb push_back
#define fi first
#define se second

// to be used with algorithms that processes a container Eg: find(all(c),42)
#define all(x) (x).begin(), (x).end() //Forward traversal
#define rall(x) (x).rbegin, (x).rend() //reverse traversal

// find if a given value is present in a container. Container version. Runs in log(n) for set and map
#define present(c,x) ((c).find(x) != (c).end())

// find version works for all containers. This is present in std namespace.
#define cpresent(c,x) (find(all(c),x) != (c).end())

#define uni(x) (x).erase(unique(all(x)), (x).end())
#define debug(x) cout<<#x<<" -> "<<x<<'\n'


using namespace std;

// Shorthand for commonly used types
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;

void fast_IO() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

class DisjSet {
    int *rank, *parent, n;
public:
    // Constructor to create and
    // initialize sets of n items.
    DisjSet(int n) {
        rank = new int[n];
        parent = new int[n];
        this->n = n;
        makeSet();
    }

    // Creates n single item sets.
    void makeSet() {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    // Finds set of given item x.
    int find(int x) {
        // Finds the representative of the set
        // that x is an element of
        if (parent[x] != x) {

            // if x is not the parent of itself
            // Then x is not the representative of
            // his set,
            parent[x] = find(parent[x]);

            // so we recursively call Find on its parent
            // and move i's node directly under the
            // representative of this set
        }

        return parent[x];
    }

    // Do union of two sets represented
    // by x and y.
    void Union(int x, int y) {
        // Find current sets of x and y
        int x_root = find(x);
        int y_root = find(y);

        // If they are already in same set
        if (x_root == y_root)
            return;

        // Put smaller ranked item under
        // bigger ranked item if ranks are
        // different
        if (rank[x_root] <= rank[y_root]) {
            int temp = x_root;
            x_root = y_root;
            y_root = temp;
        }

        parent[y_root] = x_root;

        int new_rank = rank[x_root] + rank[y_root];
        rank[x_root] = new_rank;
        rank[y_root] = new_rank;
    }

    int get_size(int x) {
        int x_root = find(x);
        return rank[x_root];
    }

    bool same_set(int x, int y) {
        return find(x) == find(y);
    }
};


void solve() {
    int n, m; cin >> n >> m;
    int mst_cost = 0;

    DisjSet dset(n);
    vector<pair<pair<int, int>, int>> edges;
    vector<pair<int, int>> ans;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.pb({{a, b}, c});
    }

    sort(all(edges), [](pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2){
        return p1.se < p2.se;
    });

    for (auto e : edges) {
        if (!dset.same_set(e.fi.fi, e.fi.se)) {
            dset.Union(e.fi.fi, e.fi.se);
            mst_cost += e.se;
            ans.pb({e.fi.fi, e.fi.se});
        }
    }

    for (auto a : ans) {
        cout << a.fi << " " << a.se << "\n";
    }

    cout << mst_cost << "\n";
}


int main(int argc, char* argv[]) {
    fast_IO();
    auto a = freopen(argv[1], "r", stdin);

    solve();

    return 0;
}