Maximum Bipartite Matching
Two groups where members can connect across groups. Find the maximum number of matched pairs.
Lessons
1. Intro
(Pairing people and tasks)
2. What Is a Matching
(No shared endpoints)
3. Maximum Matching
(Largest possible set)
4. Perfect Matching
(Everyone gets paired)
5. Augmenting Paths
Alternating matched and unm...
6. Why Augmenting Paths Work
(One more edge each time)
7. Finding Augmenting Paths
(DFS from unmatched nodes)
8. Quiz: Augmenting Paths in Matching
Knowledge check
9. Kuhn's Algorithm
Greedy augmenting path search
10. Kuhn's Algorithm - Pseudocode
(Try to match left node)
11. Problem - School Dance
(CSES 1696)
12. Problem - School Dance - Read Statement
(CSES link)
13. School Dance - Core Idea
(Bipartite matching directly)
14. School Dance - Algorithm
(DFS-based matching)
15. School Dance - Implementation
(C++ Kuhn's algorithm)
16. School Dance - Walkthrough
(3 boys 4 girls)
17. School Dance - Lessons
(Direct bipartite matching)
18. Quiz: Kuhn's Algorithm Complexity
Knowledge check
19. Reduction to Max Flow
(Flow network construction)
20. Why Max Flow Works
(Flow equals matching)
21. König's Theorem
(Matching equals vertex cover)
22. Proof Idea of König's Theorem
(Construction from matching)
23. Hall's Marriage Theorem
Condition for perfect matching
24. Checking Hall's Condition
(Exponential subsets)
25. Quiz: Hall's Marriage Theorem
Knowledge check
26. Application - Job Assignment
(Workers and tasks)
27. Application - Scheduling
(Time slots and tasks)
28. Problem - Maximum Matching
(General bipartite graph)
29. Maximum Matching - Core Idea
(Kuhn's algorithm directly)
30. Maximum Matching - Implementation
(Python version)
31. Maximum Matching - Walkthrough
(4 left 3 right)
32. Maximum Matching - Lessons
(Recursive rematching)
33. Problem - Assign Cookies
(Greedy vs matching)
34. Assign Cookies - Greedy Solution
(Two pointers)
35. Assign Cookies - Matching Solution
(Bipartite matching approach)
36. Assign Cookies - Implementation
(Greedy two pointers)
37. Assign Cookies - Lessons
(When to use matching)
38. Quiz: Konig's Theorem
Knowledge check
39. Weighted Bipartite Matching
(Maximum weight matching)
40. Online Bipartite Matching
(Nodes arrive over time)
41. Common Mistakes
Matching impl errors
42. Improvement - Early Termination
(Stop when matching is full)
43. Hopcroft-Karp Algorithm
(Faster maximum matching)
44. When to Use Each Algorithm
Kuhn vs Max Flow vs Hopcrof...
45. Minimum Vertex Cover from Matching
(König's theorem application)
46. Minimum Edge Cover
(Cover with edges)
47. Maximum Independent Set
(Complement of vertex cover)
48. Quiz: Matching and Independence
Knowledge check
49. Checklist - Bipartite Matching
(When to use)
50. Section Recap
(Maximum matching algorithms)