Bipartite Graphs
You know BFS and can traverse graphs. Some graphs split into two groups with no same-group edges.
Lessons
1. Intro
The Goal
2. What Is a Bipartite Graph?
Core definition
3. Vocabulary - 2-Coloring
The visual test
4. Vocabulary - Partition
Two disjoint sets
5. Real World Examples
Where they appear
6. The Odd Cycle Rule
Why some graphs fail
7. Visualizing the Odd Cycle
See the contradiction
8. Quiz: Bipartite Basics
Knowledge check
9. Detection Strategy
The plan
10. BFS for Detection
Level-by-level coloring
11. DFS for Detection
Recursive approach
12. Disconnected Graphs
Multiple components
13. DFS Implementation
Alternative approach
14. BFS vs DFS Trade-offs
When to use each
15. Common Mistakes
What goes wrong
16. Time and Space Complexity
Analysis
17. LeetCode 785 Is Graph Bipartite? - Problem Statement
LeetCode 785
18. LeetCode 785 Is Graph Bipartite? - Input Format
Adjacency list
19. LeetCode 785 Is Graph Bipartite? - The Color Array
Tracking state
20. LeetCode 785 Is Graph Bipartite? - Detecting Conflicts
Same color neighbors
21. LeetCode 785 Is Graph Bipartite? - The Outer Loop
Handling all components
22. LeetCode 785 Is Graph Bipartite? - Algorithm
Step by step
23. LeetCode 785 Is Graph Bipartite? - Implementation
The code
24. LeetCode 785 Is Graph Bipartite? - Walkthrough
Trace example
25. LeetCode 785 Is Graph Bipartite? - Conflict Example
When it fails
26. LeetCode 785 Is Graph Bipartite? - Lessons
summary
27. Quiz: Detection Logic
Knowledge check
28. LeetCode 886 Possible Bipartition - Problem Statement
LeetCode 886
29. LeetCode 886 Possible Bipartition - Story
The party problem
30. LeetCode 886 Possible Bipartition - Recognizing the Pattern
It's bipartite!
31. LeetCode 886 Possible Bipartition - Building the Graph
Edge list to adj list
32. LeetCode 886 Possible Bipartition - Index Handling
One-indexed vs zero-indexed
33. LeetCode 886 Possible Bipartition - Algorithm
Same core logic
34. LeetCode 886 Possible Bipartition - Implementation
The code
35. LeetCode 886 Possible Bipartition - Walkthrough
Trace example
36. LeetCode 886 Possible Bipartition - Lessons
summary
37. Quiz: Problem Recognition
Knowledge check
38. CSES 1668 Building Teams - Problem Statement
CSES
39. CSES 1668 Building Teams - Input Format
Competitive style
40. CSES 1668 Building Teams - Output Format
Print the teams
41. CSES 1668 Building Teams - Core Idea
Same algo, new output
42. CSES 1668 Building Teams - Algorithm
Step by step
43. CSES 1668 Building Teams - Implementation
The code
44. CSES 1668 Building Teams - Walkthrough
Trace example
45. CSES 1668 Building Teams - Lessons
summary
46. Quiz: Edge Cases
Knowledge check
47. What's Next
Matching preview
48. Section Recap
What we learned