Skip to content

Index

Problems

180 problems cited across the book, each with the reason it was chosen. Difficulty labels follow the page that sets them: warm-up is a first read, core is the technique of the page, hard needs one more idea.

1Graphs and Models18chapter pages

CSES 1666Building Roadswarm-upcomponents↳ A Zoo of Graphs CF 977ECyclic Componentscorecycles↳ A Zoo of Graphs SPOJ PT07YIs it a tree?warm-uptrees↳ A Zoo of Graphs CSES 1192Counting Roomswarm-upgrid, components↳ Four Ways to Store a Graph CSES 1666Building Roadswarm-upcomponents + DSU↳ Four Ways to Store a Graph SPOJ PT07YIs it a tree?warm-upm = n-1 + connectivity↳ Four Ways to Store a Graph CF 1385EDirecting Edgescoreorientation, DAG↳ Walks, Trails, Paths, Cycles CF 915DAlmost Acyclic Graphhardis one vertex on every directed cycle? test all n candidates↳ Walks, Trails, Paths, Cycles CF 1354EGraph Coloringhardbipartite sides per component, then a DP over them to hit the class sizes↳ Subgraphs, Minors and Operations CF 566FClique in the Divisibility Graphcorean induced clique is a divisibility chain↳ Subgraphs, Minors and Operations CSES 2076Necessary Roadscorebridges↳ Connectivity, Bridges, Articulation Points CSES 1685New Flight Routeshardbridges, orientation↳ Connectivity, Bridges, Articulation Points CF 1000EWe Need More Bosseshardbridge tree, diameter↳ Connectivity, Bridges, Articulation Points CSES 1666Building Roadswarm-upcomponents↳ Connectivity, Bridges, Articulation Points CSES 1668Building Teamswarm-up2-colouring↳ Bipartite Graphs and 2-Colouring SPOJ BUGLIFEBuggy… lovewarm-up2-colouring↳ Bipartite Graphs and 2-Colouring CF 1338BEdge Weight Assignmenthardparity of paths between leaves, one DFS↳ Bipartite Graphs and 2-Colouring CSES 2179Even Outdegree Edgeshardparity, matching↳ Bipartite Graphs and 2-Colouring

2Trees24chapter pages

SPOJ PT07ZLongest path in a treewarm-updiameter↳ Trees: Six Definitions of One Object CF 519EA and B and Lecture Roomscoresubtree sizes and LCA↳ Trees: Six Definitions of One Object CSES 1674Subordinateswarm-upsubtree sizes, counted bottom-up↳ Trees: Six Definitions of One Object CSES 1132Tree Distances Icorererooting↳ Distance, Radius, Eccentricity CSES 1133Tree Distances IIcoresum of distances↳ Distance, Radius, Eccentricity CF 700BConnecting Universitieshardedge contribution↳ Distance, Radius, Eccentricity CSES 1134Prüfer Codecoredecoding↳ Counting Trees: Cayley and Prüfer CF 9DHow many trees?hardDP, Catalan-ish↳ Counting Trees: Cayley and Prüfer SPOJ HIGHWAYSCounting Highwayshardmatrix-tree theorem↳ Counting Trees: Cayley and Prüfer CSES 1669Round Tripcoreundirected cycle↳ Depth-First Search CF 977ECyclic ComponentscoreDFS classification↳ Depth-First Search CSES 1679Course SchedulecoreDFS + cycle↳ Depth-First Search CF 459EPashmak and Graphhardedge orientation↳ Depth-First Search CSES 1193Labyrinthwarm-upgrid BFS↳ Breadth-First Search CSES 1194Monsterscoremulti-source BFS↳ Breadth-First Search CF 1242B0-1 MSTcoredense graph, so traverse the complement↳ Breadth-First Search CSES 1670Swap Gamecoreimplicit graph BFS↳ Breadth-First Search CSES 1131Tree Diameterwarm-uptwo BFS↳ Tree Diameter in Two Passes SPOJ PT07ZLongest path in a treewarm-uptwo BFS↳ Tree Diameter in Two Passes CF 1000EWe Need More Bosseshardbridges + diameter↳ Tree Diameter in Two Passes CSES 2079Finding a Centroidcoresubtree sizes↳ Tree Diameter in Two Passes CSES 1137Subtree Queriescoretin/tout + segtree↳ Entry/Exit Times and the Euler Tour CSES 1674Subordinateswarm-upsubtree sizes↳ Entry/Exit Times and the Euler Tour CF 339DXenia and Bit Operationscoretree-as-segtree↳ Entry/Exit Times and the Euler Tour

3Directed Graphs22chapter pages

CSES 1682Flight Routes Checkcorestrong connectivity↳ Orientations, In/Out-Degree, Strong vs Weak CF 1385EDirecting Edgescoreorientation + toposort↳ Orientations, In/Out-Degree, Strong vs Weak CSES 2179Even Outdegree Edgeshardorientation, matching↳ Orientations, In/Out-Degree, Strong vs Weak CSES 1679Course Schedulewarm-upKahn↳ DAGs and Topological Order CSES 1681Game RoutescoreDAG counting↳ DAGs and Topological Order CSES 1680Longest Flight RoutecoreDAG DP↳ DAGs and Topological Order CF 1385EDirecting Edgescoremixed graph↳ DAGs and Topological Order CSES 1683Planets and Kingdomscoreoutput components↳ Strongly Connected Components CF 427CCheckpostscoremin cost per SCC↳ Strongly Connected Components CSES 1705Forbidden CitieshardSCC + reachability↳ Strongly Connected Components CSES 1682Flight Routes Checkcoreone SCC, or exhibit a pair that breaks it↳ Strongly Connected Components CSES 1678Round Trip IIcoredirected cycle output↳ Cycles: Detection, Extraction, Feedback Sets CSES 1757Course Schedule IIcoreprint the cycle↳ Cycles: Detection, Extraction, Feedback Sets CF 977ECyclic Componentscorewhich components are pure cycles↳ Cycles: Detection, Extraction, Feedback Sets CSES 2138Reachable NodeshardDAG reachability, bitsets↳ Cycles: Detection, Extraction, Feedback Sets CSES 1750Planets Queries Icorebinary lifting↳ Functional and Permutation Graphs CSES 1751Planets Cyclescorepeel + cycle id↳ Functional and Permutation Graphs CF 25DRoads not only in Berlandwarm-upDSU on a functional model↳ Functional and Permutation Graphs CSES 1730Nim Game Iwarm-upxor↳ Games on Directed Graphs CSES 1729Stick GamecoreSprague-Grundy↳ Games on Directed Graphs CSES 2207Grundy's Gamehardmex, splitting games↳ Games on Directed Graphs CSES 1099Stair Gamehardinvariant↳ Games on Directed Graphs

4Proof Toolkit4chapter pages

CSES 1136Counting Pathscoredifference array on a tree↳ Double Counting and Averaging CSES 1674Subordinateswarm-upcount the pairs (boss, subordinate)↳ Double Counting and Averaging CSES 2101New Roads Querieshardoffline contraction + MST↳ Contraction, Induction and Lifting CF 160DEdges in MSTcoreclassify by contraction order↳ Contraction, Induction and Lifting

5Euler Tours and Hamilton Cycles11chapter pages

CSES 1691Mail Deliverycoredirected Euler circuit↳ Euler Tours: When They Exist CSES 1693Teleporters Pathcoresemi-Eulerian, directed↳ Euler Tours: When They Exist CSES 2078Eulerian Subgraphshardsubset counting↳ Euler Tours: When They Exist CSES 1691Mail Deliverycoredirected circuit↳ Hierholzer's Linear Algorithm CSES 1693Teleporters Pathcoredirected trail↳ Hierholzer's Linear Algorithm CSES 1692De Bruijn Sequencecoreexact output checker↳ De Bruijn Sequences CSES 2205Gray Codewarm-upHamiltonian cycle on Q_n, same framing↳ De Bruijn Sequences CSES 1690Hamiltonian Flightscorebitmask DP, directed↳ Held–Karp: Hamilton in O(2ⁿn²)CSES 1136Counting Pathscorepaths on a tree, contrast↳ Held–Karp: Hamilton in O(2ⁿn²)CSES 1689Knight's Tourhardbacktracking + pruning↳ Knight's Tour and Warnsdorff's Rule CSES 1624Chessboard and Queenswarm-upsame pruning style, smaller state↳ Knight's Tour and Warnsdorff's Rule

6Shortest Paths13chapter pages

CSES 1671Shortest Routes Iwarm-upstraight Dijkstra↳ Dijkstra's Algorithm CSES 1195Flight Discountcoretwo-layer state↳ Dijkstra's Algorithm CF 459EPashmak and Graphhardedge classification↳ Dijkstra's Algorithm CF 786BLegacyhardlayered/auxiliary vertices↳ Dijkstra's Algorithm CSES 1197Cycle Findingcorenegative cycle output↳ Bellman–Ford and Negative Weights CSES 1680Longest Flight Routecore"at most k edges" DP↳ Bellman–Ford and Negative Weights CSES 1672Shortest Routes IIwarm-upcontrast with Floyd↳ Bellman–Ford and Negative Weights CSES 1672Shortest Routes IIwarm-upstraight Floyd↳ Floyd–Warshall CSES 1705Forbidden Citieshardclosure + SCC↳ Floyd–Warshall CF 601AThe Two RoutescoreFloyd on the complement↳ Floyd–Warshall CF 1242B0-1 MSTcoreBFS on the complement instead of the graph↳ 0-1 BFS, Dial, Potentials, Johnson CSES 1196Flight Routeshardk shortest paths (Dijkstra with a per-vertex counter)↳ 0-1 BFS, Dial, Potentials, Johnson CSES 2121Parcel Deliveryhardmin-cost max-flow, potentials inside↳ 0-1 BFS, Dial, Potentials, Johnson

7Matrices7chapter pages

CSES 2138Reachable Nodeshardtransitive closure as a bitset DP↳ Adjacency, Incidence and Laplacian CSES 1134Prüfer Codecoredegree sequences from a matrix-free encoding↳ Adjacency, Incidence and Laplacian CSES 1136Counting Pathscorethe tree case: difference array, no powers↳ Counting Walks with Matrix Powers CSES 2181Counting Tilingshardtransfer matrix, exponentiate over width↳ Counting Walks with Matrix Powers SPOJ HIGHWAYSCounting Highwayshardexact determinant↳ The Matrix–Tree Theorem CSES 1134Prüfer Codecorethe combinatorial sibling↳ The Matrix–Tree Theorem CSES 2181Counting Tilingshardtransfer matrix, 2^b states↳ Linear Recurrences from Graphs and Matrices

8Data Structures on Trees17chapter pages

CSES 1073Towerswarm-upgreedy with an ordered container↳ Binary Heap and priority_queue CSES 1631Reading Bookswarm-upprefix sums + max↳ Binary Heap and priority_queue CSES 1666Building Roadswarm-upcomponents↳ Disjoint Set Union (Union–Find)CF 25DRoads not only in Berlandwarm-upbridges via DSU↳ Disjoint Set Union (Union–Find)CSES 1670Swap Gamecorestate graph, contrast (BFS not DSU)↳ Disjoint Set Union (Union–Find)CSES 1734Distinct Values Queriescoreoffline + last occurrence↳ Fenwick Tree (Binary Indexed Tree)CSES 2169Nested Ranges Counthardsort + BIT↳ Fenwick Tree (Binary Indexed Tree)CSES 1188Bit Inversionshardtwo BITs, careful algebra↳ Fenwick Tree (Binary Indexed Tree)CSES 1648Dynamic Range Sum Querieswarm-uppoint update↳ Segment Tree CSES 1649Dynamic Range Minimum Querieswarm-upmin, no lazy↳ Segment Tree CSES 1736Polynomial Queriescorearithmetic-progression lazy↳ Segment Tree CF 242EXOR on Segmentcoreper-bit lazy↳ Segment Tree CSES 1731Word Combinationscoretrie + DP over prefixes↳ Trie (Prefix Tree) and Its Relatives CSES 1753String MatchingcoreKMP / automaton, the trie's cousin↳ Trie (Prefix Tree) and Its Relatives CSES 2102Finding Patternshardmany patterns, many texts↳ Trie (Prefix Tree) and Its Relatives CSES 1647Static Range Minimum Querieswarm-updirect application↳ Sparse Table and RMQ CSES 1137Subtree QueriescoreEuler order + static vs dynamic contrast↳ Sparse Table and RMQ

9Hardness and Escape Routes4chapter pages

CF 1198CMatching vs Independent Sethardthe reduction is the solution: greedily take edges, the leftovers are independent↳ The NP-complete Graph Problems Worth Knowing CSES 2181Counting Tilingshardthe "hard" problem with a small width promise↳ The NP-complete Graph Problems Worth Knowing CSES 1690Hamiltonian Flightscoresubset DP, directed↳ Escape Routes: What To Do When It Is NP-Hard CSES 1158Book Shopwarm-upthe DP-size arithmetic, in public↳ Escape Routes: What To Do When It Is NP-Hard

10Lowest Common Ancestor8chapter pages

CSES 1687Company Queries Iwarm-upk-th ancestor↳ LCA by Binary Lifting CSES 1688Company Queries IIcoreLCA↳ LCA by Binary Lifting CSES 1135Distance Queriescoredist via LCA↳ LCA by Binary Lifting CF 342EXenia and TreehardLCA inside centroid decomposition↳ LCA by Binary Lifting CSES 2079Finding a Centroidwarm-upthe answer is decided at finish time — one DFS, no table↳ Tarjan's Offline LCA CSES 1135Distance Queriescorere-solve it offline: one DFS + DSU instead of a lifting table↳ Tarjan's Offline LCA CSES 1136Counting Pathscorethe "many paths on a tree" pattern with a difference array — the offline sibling of virtual trees↳ Virtual Trees CSES 1137Subtree Querieswarm-upthe flattening that makes the virtual-tree idea natural↳ Virtual Trees

11Advanced Tree Algorithms16chapter pages

CSES 1666Building Roadswarm-upthe unweighted case: MST weight = components - 1↳ Minimum Spanning Tree CF 160DEdges in MSTcoreclassify every edge: in some / every / no MST↳ Minimum Spanning Tree CF 600ELomsat gelralcorethe standard small-to-large statement↳ Small-to-Large Merging CSES 1137Subtree Querieswarm-upthe flattening alternative — compare the two approaches on the same data↳ Small-to-Large Merging CSES 2079Finding a Centroidwarm-upthe single-level version↳ Centroid Decomposition CF 342EXenia and Treehardthe dynamic nearest-marked pattern, O(log² n) per operation↳ Centroid Decomposition CSES 1133Tree Distances IIcorecentroid is overkill here — know why rerooting wins↳ Centroid Decomposition SPOJ QTREEQuery on a treehardmax edge on a path with updates — the benchmark for HLD↳ Heavy-Light Decomposition CSES 1135Distance Queriescoresolve with HLD's lca to compare code size against lifting↳ Heavy-Light Decomposition CSES 1137Subtree Querieswarm-upthe interval half of the same machinery↳ Heavy-Light Decomposition CSES 1700Tree Isomorphism Icorerooted, canonical hash↳ Tree Hashing and Isomorphism CSES 1701Tree Isomorphism IIhardunrooted — center-based reduction↳ Tree Hashing and Isomorphism CSES 1674Subordinateswarm-upthe subtree-shape information hashing builds on↳ Tree Hashing and Isomorphism CSES 1631Reading Bookswarm-upthe "max vs half" edge case where Huffman-style merging degenerates↳ Huffman Coding CSES 1073Towerswarm-upthe same "extract an extreme from a heap" skeleton, different greedy↳ Huffman Coding CF 9DHow many trees?hardcounting the trees Huffman builds: DP over (nodes, depth) instead of merging them↳ Huffman Coding

12Cuts and Flows10chapter pages

CSES 1694Download Speedcoremax flow on a small dense graph — parallel edges must be summed↳ Cuts and Flows CSES 1695Police Chasecoreedge-disjoint paths = unit-capacity max flow↳ Cuts and Flows CSES 1694Download Speedcoreparallel edges and capacity types↳ Max Flow: Ford–Fulkerson, Dinic, Push–Relabel CSES 1695Police Chasecoreunit capacities, edge-disjoint paths↳ Max Flow: Ford–Fulkerson, Dinic, Push–Relabel CSES 1711Distinct Routeshardrecover k edge-disjoint paths from the flow decomposition↳ Max Flow: Ford–Fulkerson, Dinic, Push–Relabel CSES 2130Distinct Routes IIhardvertex capacities: split every vertex↳ Max Flow: Ford–Fulkerson, Dinic, Push–Relabel CSES 1695Police Chasecorethe min cut is the minimum set of roads to close — read it off the residual graph↳ Min-Cut Models CSES 2130Distinct Routes IIhardvertex-disjoint paths: vertex splitting turns "delete a vertex" into a unit-capacity cut↳ Min-Cut Models CSES 2121Parcel Deliveryhardexactly the K-unit min-cost flow statement↳ Min-Cost Max-Flow CSES 1694Download Speedwarm-upthe same graph with no costs: plain max flow is 20x faster — know which one you need↳ Min-Cost Max-Flow

13Matching14chapter pages

CSES 1696School Dancecorethe bipartite matching statement with output pairs↳ Matching: Definitions and Duality CSES 1130Tree Matchingwarm-upmaximum matching on a tree is DP, not flow — know both↳ Matching: Definitions and Duality CSES 1696School Dancecoreoutput the pairs, not just the size↳ Bipartite Matching (Kuhn's Algorithm)CSES 1130Tree Matchingwarm-upthe same objective on a tree, where DP beats augmenting paths↳ Bipartite Matching (Kuhn's Algorithm)CSES 1130Tree Matchingwarm-upsame objective, and HK is the wrong tool — see why↳ Hopcroft–Karp CSES 1696School DancecoreHK and Kuhn on the same input; time both if you can↳ Hopcroft–Karp CSES 1696School Dancecoreextend it: also print a minimum set of students+parents that "touches" every acceptable pair↳ Kőnig's Theorem and Minimum Covers CSES 1130Tree Matchingwarm-upon a tree the cover dual is the same DP with a second state — derive it and check it matches the matching size↳ Kőnig's Theorem and Minimum Covers CSES 2121Parcel Deliveryhardflow-with-costs — the case where MCMF is the right tool and Hungarian is not↳ The Hungarian Algorithm CSES 1631Reading Bookswarm-upa "pairing" instance with no matching needed — a good calibration of when not to reach for the algorithm↳ The Hungarian Algorithm CSES 1696School Dancecoremaximum matching with explicit output — the base of every reduction above↳ Matching Applications CSES 2181Counting Tilingshardthe counting version: DP, not matching — the contrast is the lesson↳ Matching Applications CSES 1696School Dancewarm-upre-solve it with a general-graph matching routine and compare the code length↳ General Matching and Blossoms CSES 1130Tree Matchingcorea graph where blossoms can never appear: prove the DP is enough because there are no odd cycles↳ General Matching and Blossoms

14Special Topics12chapter pages

CSES 1666Building Roadswarm-upthe word "roads" is not a planarity hypothesis — a calibration exercise in reading↳ Planarity and Euler's Formula CSES 1752Creating Officesharddominating-set style; planar-greedy intuitions fail here, and it is worth seeing why↳ Planarity and Euler's Formula CSES 1134Prüfer Codewarm-upthe tree case: degree of v = occurrences of v + 1, exactly why ∑ d_i = 2n-2↳ Degree Sequences and Graphical Sequences CSES 2138Reachable Nodescoredegree-sequence intuition versus actual reachability — a useful reality check↳ Degree Sequences and Graphical Sequences CSES 1668Building Teamswarm-upthe 2-colouring case, in public↳ Graph Colouring CSES 1684Giant Pizzacore2-SAT, i.e. "2-colouring with clauses" — see 2-SAT↳ Graph Colouring CSES 1684Giant Pizzacorethe textbook 2-SAT instance: two toppings per pizza, contradictory preferences↳ 2-SAT CSES 1682Flight Routes Checkwarm-upthe SCC machinery you need, without the SAT part↳ 2-SAT CSES 1751Planets Cyclescorefunctional-graph walk length until repetition — the deterministic twin↳ Random Walks and Cover Times CSES 1750Planets Queries Iwarm-up"where is the walk after k steps": lifting, not expectations↳ Random Walks and Cover Times CSES 1130Tree Matchingwarm-upthe two-state DP in its simplest form (the dual of independent set on a tree)↳ Independent Sets, Cliques, and Treewidth CSES 1696School Dancecorethe bipartite route to α = n - ν: solve it with matching and compare with the DP↳ Independent Sets, Cliques, and Treewidth