Topological Sort
Kahn's algorithm (BFS-based), DFS-based topological sort, and cycle detection in directed graphs.
Lessons
1. Intro
Getting Dressed
2. Directed Acyclic Graphs (DAGs)
No Circles Allowed
3. Kahn's Algorithm - The Intuition
Peeling the Onion
4. Kahn's Algorithm - Implementation
The Template
5. Detecting Cycles with Kahn's
The Leftovers
6. Quiz: Cycle Detection with Kahn's
Knowledge check
7. Problem - Course Schedule II
LeetCode 210
8. Course Schedule II - The Constraint
Building dependencies
9. Course Schedule II - Core Idea
In-degree tracks readiness
10. Course Schedule II - Algorithm
Kahn's step by step
11. Course Schedule II - Implementation
The code
12. Lessons from Course Schedule II
What you learned
13. DFS-Based Topological Sort
Alternative to Kahn
14. Comparing Kahn and DFS
When to use each
15. Quiz: Kahn's vs DFS Topological Sort
Knowledge check
16. Common Topological Sort Mistakes
Pitfalls to avoid
17. Pattern - Lexicographical Order
Controlling the Choice
18. Pattern - Uniqueness
Is there only one way?
19. Pattern - Implicit Graphs
Deriving Edges
20. Dynamic Programming on DAGs
The Real Power
21. Quiz: DAG Properties
Knowledge check
22. Problem - Longest Flight Route
The code
23. Longest Flight Route - Core Idea
DP on topological order
24. Longest Flight Route - Algorithm
Kahn's + DP
25. Longest Flight Route - Implementation
CSES 1680
26. Pattern - Reverse Logic
Flip the edges
27. Lessons from Longest Flight Route
DAG DP pattern
28. Quiz: DP on DAGs
Knowledge check
29. Problem - Game Routes
CSES 1681
30. Game Routes - Core Idea
Summing paths instead of max
31. Game Routes - Algorithm
Topological order guarantees
32. Game Routes - Implementation
The code
33. Lessons from Game Routes
Counting on DAGs
34. Quiz: Counting Paths in a DAG
Knowledge check
35. Problem - Parallel Courses III
LeetCode 2050
36. Parallel Courses III - Core Idea
Finish time propagates
37. Parallel Courses III - Algorithm
DP on topological order
38. Parallel Courses III - Implementation
The code
39. Lessons from Parallel Courses III
Critical Path Method
40. Quiz: Parallel Scheduling
Knowledge check
41. Section Recap
Order from Chaos