DAG and Topological Sort
You've detected cycles. Now use topological order for scheduling. Solve Course Schedule variants and learn DP on directed acyclic graphs.
Lessons
1. Introduction to DAGs and Topological Sort
No cycles, can be ordered
2. What DAG Problems Solve
Build systems, task scheduling
3. When to Use Topological Sort
Dependencies → topological order
4. Kahn's vs DFS Topological Sort
Comparing the approaches
5. Problem - Alien Dictionary
LC 269 - character order from sorted words
6. Alien Dictionary - Why Naive Fails
Adjacent words reveal one ordering
7. Alien Dictionary - Building the Graph
Edge from c1 → c2 means c1 < c2
8. Alien Dictionary - Transition
First differing character gives edge
9. Alien Dictionary - Base Cases
Longer word before prefix = invalid
10. Alien Dictionary - Implementation
Build graph, run topo sort
11. Alien Dictionary - Time and Space
O(C) total characters processed
12. Problem - Longest Increasing Path
LC 329 - longest strictly increasing path
13. Longest Increasing Path - Why Naive Fails
Strictly increasing = no cycles
14. Longest Increasing Path - Defining the DP
dp[r][c] = longest from this cell
15. Longest Increasing Path - Core Logic
Recurse into larger neighbors
16. Longest Increasing Path - Implementation
Memoization avoids recomputation
17. DP on DAG Pattern
The DAG DP pattern
18. Problem - Find All Recipes
LC 2115 - recipes from ingredients
19. Find All Recipes - Solution
Supplies have in-degree 0
20. Find All Recipes - Why This Works
Process available ingredients first
21. Problem - Parallel Courses
LC 1136 - minimum semesters
22. Parallel Courses - Solution
Level-by-level with Kahn's
23. Quiz: Topological Sort Applications
Which topo sort pattern?
24. Quiz: DAG Properties
Cycle detection methods
25. Common Mistakes in DAG Problems
Missing in-degree update, wrong order
26. Problem - Largest Color Value
LC 1857 - color propagation
27. Largest Color Value - Solution
The solution
28. Section Recap
Kahn's to DFS cycle detection