Intermediate · Module 17 · Lesson 10
Strongly connected components
Kosaraju and Tarjan decompositions.
15–25 min readLesson 104 of 123
Lesson 104 of 123
1d streakTheory lesson · Step-by-step
Understand Strongly connected components
Kosaraju and Tarjan decompositions.
Worked approach
Trace the reasoning step by step
- 1Compute DFS finish order or low-link values.
- 2Traverse in the required second order.
- 3Collect one component at a time.
- 4Condense components into a DAG when useful.
Concrete example
Decompose edges 0→1, 1→0, and 1→2.
- 10 and 1 reach each other.
- 22 cannot return to them.
Components are {0,1} and {2}.
What must remain true (Loop Invariant)
Every produced component is maximal: each pair of its vertices can reach one another.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Graph processing
O(V + E)
O(V)
Assumes adjacency-list representation unless stated otherwise.When to use it
- Networks, dependencies, connectivity, shortest paths, and grid movement.
- Ordering prerequisite-constrained work.
- Grouping reachable or mutually reachable states.
Common mistakes
- Marking visited too late and enqueuing the same vertex repeatedly.
- Ignoring disconnected components.
- Using an algorithm whose weight assumptions do not match the graph.
Practice prompts
- Reproduce the worked Strongly connected components example without looking at the trace.
- Change one input condition and explain whether the Strongly connected components invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.