🧠 The Big Picture
Week 3 gave you two greedy/ordering paradigms. Topological sort = linearize a DAG by
dependencies (Kahn's peel-from-front, or DFS finish-time). MST = connect everything at
minimum cost (Kruskal's global-greedy, or Prim's grow-a-tree). Today is about fast recognition
— spotting which paradigm a disguised problem needs.
🧭 Recognition Flowchart
| Signal in the problem | Algorithm |
|---|
| "Prerequisites," "must come before," "build/compile order," "dependencies" | Topological sort (Kahn's or DFS) |
| "Circular dependency," "deadlock," "can everything finish?" | Directed cycle detection (Kahn count / 3-color DFS) |
| "Minimum semesters / rounds," "longest chain in a DAG" | Layered Kahn's / DP over topo order |
| "Connect all X at minimum total cost," "no redundant links" | MST (Kruskal / Prim) |
| "Complete/geometric graph, connect points" | MST — Prim O(V²) (avoid building all edges) |
| "Some connections free / pre-built" | MST — union free edges first |
| "Minimize the maximum edge on a path" | MST (bottleneck property) |
| "Which edges are essential to the MST?" | Critical/pseudo-critical edge analysis |
🎭 Master Variance Cheat-Sheet (Big Tech favorites)
Topological Sort family
| Variance | Key adaptation |
|---|
| Just feasibility (cycle?) | Kahn count == V, or 3-color DFS |
| Return the order | Collect output; empty if cycle |
| Unique order? | Kahn's queue must hold ≤1 node at all times |
| Lexicographically smallest | Replace queue with min-heap |
| Min rounds / parallel scheduling | Count Kahn BFS layers (longest path) |
| Order inferred from data (alien dict) | Extract edges from adjacent pairs first |
| Eventual safe / doomed nodes | Color DFS or reverse-graph Kahn |
MST family
| Variance | Key adaptation |
|---|
| Plain min total cost | Kruskal or Prim, return weight |
| Dense/complete graph | Prim O(V²), don't materialize all edges |
| Virtual super-source (wells/hubs) | Add node 0 with special edges |
| Pre-connected components | Union free edges before Kruskal |
| Maximum spanning tree | Sort edges descending |
| Bottleneck (minimize max edge) | MST already minimizes it |
| K clusters remaining | Stop after V−k safe edges |
| Critical / pseudo-critical edges | Force/exclude each edge, compare MST weight |
🔁 Recall Drill (~40 min)
From memory, on a blank file, reproduce:
- Kahn's topo sort with the cycle check.
- 3-color DFS cycle detection.
- Kruskal's (reusing your Day 9 Union-Find).
- Prim's with a min-heap.
If Kruskal and Prim blur together, anchor on: Kruskal sorts edges + Union-Find; Prim grows a tree + heap. Both rely on the cut property.
🎯 Timed Problems (~80 min)
LC 1489
Find Critical and Pseudo-Critical Edges in MST
The premier MST-variance question — force/exclude each edge, compare weights.
Hard
LC 444
Sequence Reconstruction
Uniqueness variance — Kahn's queue must never exceed size 1.
Med
LC 1203
Sort Items by Groups Respecting Dependencies
Two-level topo sort (groups, then items) — a hard composition. Optional stretch.
Hard
✅ Week 3 Exit Check
Ready for Week 4 (Advanced) if you can, without notes:
- Write Kahn's and 3-color DFS in < 8 min each, both with cycle detection.
- State the cut property and use it to justify both Kruskal and Prim.
- Pick Kruskal vs Prim based on graph density and defend the choice.
- Recognize a disguised MST or topo problem within ~1 minute of reading it.
Next up: Week 4 goes advanced — Tarjan's SCC/bridges, bipartite checking, Eulerian paths, A*, and a taste of network flow.