Chapter 77

Home

Refactoring: Kruskal with Union-Find

DFS cycle-check makes Kruskal O(E×V). Union-Find reduces it to O(E α(V)) — effectively O(E log V) due to sorting. This is the version you'll use in every contest.

Before: O(E×V) with DFS

C++ — O(E×V) cycle check

if (are_connected(tree, e.u, e.v)) continue;  // O(V)

After: O(E log V) with Union-Find

C++ — Kruskal with DSU

struct Edge { int u, v, w; };

int kruskal(vector& edges, int V) {
    sort(edges.begin(), edges.end(),
         [](auto& a, auto& b) { return a.w < b.w; });

    DSU dsu(V);
    int total = 0, added = 0;

    for (auto& e : edges) {
        if (dsu.same(e.u, e.v)) continue;  // O(α(V)) — near O(1)
        dsu.unite(e.u, e.v);
        total += e.w;
        added++;
        if (added == V - 1) break;
    }
    return total;
}

// O(E log E) for sorting + O(E α(V)) for unions = O(E log V)

Rust — Kruskal with DSU

fn kruskal(edges: &mut [(usize, usize, i32)], v: usize) -> i32 {
    edges.sort_by_key(|e| e.2);
    let mut dsu = DSU::new(v);
    let mut total = 0;
    let mut added = 0;

    for &(u, v, w) in edges.iter() {
        if dsu.same(u, v) { continue; }
        dsu.unite(u, v);
        total += w;
        added += 1;
        if added == v - 1 { break; }
    }
    total
}

💡 Kruskal vs Prim

Kruskal is O(E log V) — better for sparse graphs. Prim with PQ is O((V+E) log V) — better for dense graphs. In practice, Kruskal is simpler to implement correctly.

Key Takeaways