Pattern #62

Sorted-edge MST construction, Union Find cycle prevention, component merging, virtual nodes, critical edges, and Go templates.

Must Solve

15 core questions.

1. 1.Min Cost to Connect All Points
   medium
2. 2.Connecting Cities With Minimum Cost
   medium
3. 3.Optimize Water Distribution in a Village
   medium
4. 4.Minimum Cost to Connect All Nodes
   medium
5. 5.Redundant Connection — DSU Relation
   medium
6. 6.Find Critical and Pseudo-Critical Edges in MST
   medium
7. 7.Minimum Spanning Tree from Edge List
   hard
8. 8.Minimum Cost to Connect Components
   hard
9. 9.Minimum Spanning Forest
   hard
10. 10.Maximum Spanning Tree — Variant
    hard
11. 11.MST With Pre-Connected Nodes
    hard
12. 12.MST With Virtual Node
    hard
13. 13.Minimum Cost to Connect Islands
    hard
14. 14.Edge Classification in MST
    hard
15. 15.Second Minimum Spanning Tree — Advanced
    hard

Also Important

1. 16.Earliest Acquaintance / Connectivity by Sorted Events
   medium
2. 17.Minimum Cost Network Construction
   medium
3. 18.Offline Connectivity Queries
   medium
4. 19.Manhattan MST — Advanced
   medium
5. 20.Dynamic MST — Advanced
   medium

How to Think

Sort every edge by weight
↓
Find roots of both endpoints
↓
Different roots? Union + take edge
Same root? Reject cycle
↓
Stop after V − 1 accepted edges

Go Quick Reference — Kruskal + DSU

sort.Slice(edges, func(i, j int) bool {
    return edges[i].weight < edges[j].weight
})

cost, used := 0, 0
for _, edge := range edges {
    if dsu.Union(edge.u, edge.v) {
        cost += edge.weight
        used++
        if used == n-1 { break }
    }
}
if used != n-1 { return -1 } // disconnected
return cost

Union must compare representative roots. Path compression plus union by size makes DSU operations almost constant amortized time.

DSU & Kruskal Variants

Sort edges → cheapest first
Different roots → accept + Union
Same root → reject cycle
Accepted edge → add cost
V − 1 accepted → MST complete

Complexity

Sort edges: O(E log E)
DSU work:  O(E α(V))
Total:     O(E log E)
Space:     O(V + E)

Common Interview Mistakes

• Forgetting to sort edges

• Taking every cheap edge without a cycle check

• Comparing parent values instead of Find roots

• Adding weight when Union fails

• Not verifying V − 1 accepted edges

• Using Kruskal for a shortest-path question

• Treating directed edges as a normal MST

• Assuming equal weights imply a unique MST

Interview Rules

Edge-list MST       → Kruskal
First step          → sort by weight
Cycle check         → Find(u) == Find(v)
Safe edge           → Union succeeds
Cost update         → only after successful Union
Completion          → V − 1 edges
Disconnected        → forest or failure

Kruskal → edge-list MST
First → sort edges
Cycle test → Find roots
Accept → successful Union
Cost → add only accepted edge
Stop → V − 1 edges
Time → O(E log E)

💡 Golden Rule: Process edges from cheapest to most expensive and accept one only when it merges two different components.