8. Kruskal's (MST)

Given a graph G = (V,E) we want to find a Minimum Spanning Tree in the graph (it may not be unique).

A minimum spanning tree is a subset of the edges which connect
all vertices in the graph with the minimal total edge cost.

Steps:

1. Sort edges by ascending edge weight.

2. Walk through the sorted edges and look at the two nodes the edge belongs to, if the nodes are already unified we don’t include this edge, otherwise we include it and unify the nodes.

3. The algorithm terminates when every edge has been processed or all the vertices have been unified.

// edges = {weight, u, v}

int kruskal(int V, vector<vector<int>>& edges) {

    // Sort edges in increasing order of weight
    sort(edges.begin(), edges.end());

    DSU dsu(V);

    int mstWeight = 0;

    vector<vector<int>> mst;

    // Process every edge
    for (auto &edge : edges) {

        int weight = edge[0];
        int u = edge[1];
        int v = edge[2];

        // If the edge connects two different components,
        // include it in the MST.
        if (dsu.unite(u, v)) {

            mstWeight += weight;

            mst.push_back({u, v, weight});
        }
    }

    // If the graph is disconnected,
    // MST cannot be formed.
    if (mst.size() != V - 1)
        return -1;

    return mstWeight;
}