Kruskal's Algorithm (MST)

Concept

Kruskal's algorithm finds the Minimum Spanning Tree (MST) by sorting all edges by weight and greedily adding the cheapest edge that doesn't form a cycle. It uses DSU (Union-Find) to efficiently check if two nodes are already connected.

When to Use

▸Finding the minimum cost to connect all nodes in a graph
▸Minimum spanning tree problems
▸Network design (minimum cable/road to connect all cities)
▸When edges are given as a list (edge-list representation)

Intuition

Imagine you're building roads between cities and want minimum total cost. Sort all possible roads by cost. Pick the cheapest road — if it connects two previously disconnected groups of cities, build it. If both cities are already connected (via other roads), skip it to avoid a cycle. Repeat until all cities are connected. DSU tells us instantly whether two cities are in the same group.

Complexity

Time

O(E log E)

Space

O(V + E)

Template Code

cpp

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

vector<int> parent;

int findRoot(int n){
    if(n == parent[n]) return n;
    return parent[n] = findRoot(parent[n]);
}

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

    int n, m;
    cin >> n >> m;

    parent.resize(n+1);
    for(int i = 0; i < n+1; i++) parent[i] = i;

    vector<pair<int, pair<int, int>>> edges;

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

    sort(edges.begin(), edges.end());

    int A, B, used = 0;
    long long cost = 0;
    for(int i = 0; i < m; i++){
        a = edges[i].second.first;
        b = edges[i].second.second;
        A = findRoot(a);
        B = findRoot(b);

        if(A != B){
            parent[A] = B;
            cost += edges[i].first;
            used++;
        }
    }

    if(used != n-1) cout << "IMPOSSIBLE\n";
    else cout << cost << "\n";

    return 0;
}

// Sample Input:
// 5 7
// 1 2 2
// 1 3 3
// 2 3 1
// 2 4 4
// 3 4 5
// 3 5 6
// 4 5 7
//
// Sample Output:
// 16