Strongly Connected Components
Mutual reachability in directed graphs. Kosaraju and Tarjan algorithms. The condensation DAG.
Lessons
1. Intro
(Why this section matters)
2. What is an SCC?
(Mutual reachability)
3. Why Find SCCs?
(Compression and structure)
4. Kosaraju's Algorithm - Intuition
(Two DFS passes)
5. Kosaraju's Algorithm - Steps
(Implementation outline)
6. Kosaraju Example
(4-node directed graph)
7. Kosaraju - Implementation
(C++ code)
8. Quiz: Kosaraju's First DFS
Knowledge check
9. Tarjan's Algorithm - Intuition
(Single DFS with low-link)
10. Tarjan's Algorithm - Steps
(Discovery and low-link)
11. Tarjan Example
(Same 4-node graph)
12. Tarjan - Implementation
(C++ code)
13. Kosaraju vs Tarjan
(When to use which)
14. Quiz: Tarjan's Low-Link Values
Knowledge check
15. The Condensation Graph
(DAG of SCCs)
16. Building the Condensation Graph
(Implementation)
17. Application: Dependency Analysis
Package managers, build sys...
18. Application: 2-SAT Connection
(Boolean satisfiability)
19. Quiz: Condensation Graph
Knowledge check
20. Problem - Planets and Kingdoms (CSES 1683)
(CSES 1683 intro)
21. Planets and Kingdoms - Approach
(SCC detection)
22. Planets and Kingdoms - Implementation
(C++ code)
23. Problem - Coin Collector (CSES 1686)
(CSES 1686 intro)
24. Coin Collector - Approach
(SCC + DAG DP)
25. Coin Collector - Implementation
(C++ code)
26. Problem - Flight Routes Check (CSES 1682)
(CSES 1682 intro)
27. Flight Routes Check - Approach
(SCC count)
28. Flight Routes Check - Implementation
(C++ code)
29. Quiz: SCC Problem Solving
Knowledge check
30. Edge Cases for SCC Problems
(Self-loops and single nodes)
31. Common SCC Mistakes
(Debugging tips)
32. SCC in Undirected Graphs?
(Why it doesn't apply)
33. When to Use SCC
(Problem recognition)
34. Practice Problem 1
(SCC detection)
35. Practice Problem 2
(Condensation graph DP)
36. Practice Problem 3
(Reachability check)
37. SCC and Bridges/Articulation Points
(Different concepts)
38. SCC in Real-World Graphs
(Web, social, citation)
39. Time Complexity Summary
(Both algorithms)
40. Space Complexity Summary
(Memory usage)
41. SCC and Cycle Detection
(Finding directed cycles)
42. SCC and Topological Sort
(No direct connection)
43. Quiz: SCC and Cycle Detection
Knowledge check
44. SCC Templates
(Code references)
45. Section Recap
(What you learned)