Kruskal and DSU

Sort edges by weight, accept safe edges, and use Union-Find to detect cycles. · 13 min read

Concept

Kruskal's algorithm sorts every edge by weight and scans from cheapest to most expensive. It accepts an edge if it connects two different components; otherwise it rejects the edge because it would create a cycle.

Interactive visualization: Kruskal: sorted edges plus DSU components — step through it frame by frame on this page.

The algorithm

sort(edges.begin(), edges.end()); // by weight
DSU dsu(n);
long long total = 0;
int used = 0;

for (auto [w, u, v] : edges) {
    if (dsu.find(u) != dsu.find(v)) {
        dsu.unite(u, v);
        total += w;
        used++;
    }
}

if (used != n - 1) cout << "no spanning tree\n";
else cout << total << '\n';

Union-Find / DSU

A disjoint set union structure tracks which component each vertex belongs to. find(x) returns the representative of x's component. unite(a, b) merges two components. With path compression and union by rank/size, each operation is nearly constant amortized time.

Interactive visualization: DSU simulation: find, compress, unite — step through it frame by frame on this page.

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    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);
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

Why Kruskal is correct

Cut-property proof sketch

consider the next cheapest edge e = (u, v) — Kruskal scans edges in nondecreasing weight.
u and v are in different components — The current forest creates a cut between those components.
e is the cheapest edge crossing that cut among unprocessed safe choices — Any cheaper crossing edge would have appeared earlier.
by the cut property, e is safe — There exists an MST containing every accepted edge so far plus e.

Result: Kruskal builds an MST by repeatedly adding safe edges

Complexity

Sorting dominates: O(E log E) time. DSU operations contribute O(E alpha(V)), where alpha is the inverse Ackermann function and is effectively constant for real input sizes. Space is O(V) for DSU plus O(E) for the edge list.

Practice: Minimum Connection Cost (Medium) — Return the MST weight of a weighted undirected graph, or -1 if disconnected.