ZERO / HERO
Cheapest cables first

Kruskal's MST

The analogy

You must connect every building with cable, using as little cable as possible. Sort every possible cable run from cheapest to most expensive, then lay them one by one — but skip any cable joining two buildings that are already connected somehow, because that would just make a redundant loop.

Visualizer

Cheapest edge that does not cycle

step 1 / 9
ABCDEF

Connect every town with minimum total cable. Kruskal sorts all edges cheapest-first and never looks at the graph structure again.sorted: AC2, CE3, AB4, ED4, BC5, EF5, BD10, DF11

def kruskal(n, edges):        # edges: (w, u, v)
    dsu = DSU(n)
    mst, total = [], 0
    for w, u, v in sorted(edges):        # cheapest first
        if dsu.union(u, v):              # False => cycle, skip
            mst.append((u, v, w))
            total += w
        if len(mst) == n - 1:
            break                        # spanning tree complete
    return mst, total

# O(E log E) — the sort dominates
# maximum spanning tree: sorted(edges, reverse=True)
Check yourself

Kruskal skips an edge. Why?