Chapter 3
Directed Graphs
Orientation breaks symmetry — and gives you order. Once you can collapse a digraph to its DAG of strongly connected components, half of “impossible ordering” problems become plain DP on a DAG.
7 pages4,799 words22 problems2 interactive
1Orientations, In/Out-Degree, Strong vs WeakWhat changes when edges get arrows — and the degree identities that survive.2DAGs and Topological OrderTwo algorithms, one equivalence, and DP on a DAG as the default solution shape.3Strongly Connected ComponentsKosaraju and Tarjan in linear time, why the second pass needs the transpose, and the condensation as a working object.4Cycles: Detection, Extraction, Feedback SetsFind one cycle in linear time, find the shortest one, and know what "remove the fewest vertices to make it a DAG" costs.5TournamentsEvery pair plays once: scores, the king chicken theorem, and the Hamiltonian path you get for free.6Functional and Permutation GraphsOne out-edge per vertex: cycles with trees hanging off them, and the binary-lifting that navigates them.7Games on Directed GraphsPositions, moves, and the winning/losing labelling that solves every impartial finite game.