Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 19m 31s17 days 22 hours 19 minutes 31 seconds.

Advanced - Graphs · 4:34

Strongly Connected Components & Condensation

A strongly connected component is a maximal set of vertices that all reach each other; the components partition the graph, and shrinking each to a point gives the condensation, which is always a DAG. Kosaraju's algorithm finds them with two depth-first searches: record finishing order, then search the reversed graph in decreasing finishing order, getting the components in topological order. Tarjan's one-pass algorithm uses low values and a stack and closes them in reverse order.

You will learn

Define strongly connected components and explain why the condensation is always a DAG
Run Kosaraju's two passes and explain, with the finishing-time theorem, why each pass-2 search claims exactly one component
Use the topological order of components for DP on the condensation and for the max(#sources, #sinks) edge-augmentation count
Implement Tarjan's algorithm with the on-stack check and know that it produces components in reverse topological order

Chapters

PreviousStrong Orientation (Robbins' Theorem)Next2-SAT