Minimum spanning tree

Connect all vertices with minimum total edge weight. Kruskal’s algorithm takes cheap edges without creating cycles.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Sort undirected edges by weight.
2. Use DSU to check whether endpoints are in different components.
3. Accept an edge only when it merges components.
4. A connected graph finishes with n−1 edges; otherwise the result is a minimum spanning forest.
5. The DSU rejects precisely the edges that would close a cycle. The cut property certifies the cheapest edge joining distinct current components. long long stores the total.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: The DSU rejects precisely the edges that would close a cycle. The cut property certifies
// the cheapest edge joining distinct current components.
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
struct DSU{
    vector<int>p,sz;
    DSU(int n):p(n+1),sz(n+1,1){
        iota(p.begin(),p.end(),0);
    }
    int find(int v){
        return p[v]==v?v:p[v]=find(p[v]);
    }
    bool unite(int a,int b){
        a=find(a);
        b=find(b);
        if(a==b){
            return false;
        }
        if(sz[a]<sz[b]){
            swap(a,b);
        }
        p[b]=a;
        sz[a]+=sz[b];
        return true;
    }
};
struct Edge{
    int u,v,w;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<Edge>edges(m);
    for(Edge&edge:edges){
        cin>>edge.u>>edge.v>>edge.w;
    }
    sort(edges.begin(),edges.end(),[](Edge a,Edge b){
        return a.w<b.w;
    });
    DSU ds(n);
    long long total=0;
    int taken=0;
    for(auto e:edges){
        if(ds.unite(e.u,e.v)){
            total+=e.w;
            ++taken;
        }
    }
    if(taken!=n-1){
        cout<<"Disconnected\n";
    }
    else{
        cout<<total<<"\n";
    }
}

Complexity analysis

O(E log E) time, O(V + E) space including edges.

Example input and output

Read n m, then m undirected edges a b weight. Require n≥1, m≤200000 and |weight|≤10^9. Print the MST weight or Disconnected. Negative weights and parallel edges are allowed.

Input

4 4
1 2 4
2 3 -1
3 4 2
1 4 7

Output

5

Kruskal accepts weights -1, 2, and 4. These three edges connect all four vertices for total 5.

Practical applications

Use Kruskal to connect all vertices at minimum total weight. Compare Prim when a dense adjacency representation is already available.

Check your understanding

For n vertices, how many edges does a spanning tree have?

Put it into practice

Find the cheapest set of cables that connects every city.