Skip to content
Tutorials Center
My learning

Topics

Lesson 57 of 63 ยท Practice and Review

CSES Graph Problems Walkthrough

Original walkthrough of classic CSES graph problems: grid BFS, multi-source BFS, negative cycles, Dijkstra with state, binary lifting, Hamiltonian counting and Euler circuits in Python.

The Graph Algorithms section of the CSES Problem Set is the largest one, with about 35 problems. They are well chosen: each one is a standard algorithm with a small twist that forces you to understand it, not just recall it. Shortest paths in a grid, negative cycles, Dijkstra with an extra state, jumping through a functional graph, counting Hamiltonian paths and Euler tours all appear.

This lesson explains seven of the most instructive problems and gives original Python for each, tested against an independent brute force. The statements are my own paraphrases; solve the originals on the CSES site first. Background reading: Graph Problems: Modeling and Traversal and Shortest Paths in Practice.

flowchart TD
    P["Graph problem"] --> G{"What are the edges?"}
    G -- "grid cells" --> BFS["BFS, maybe multi-source"]
    G -- "weighted, non-negative" --> DJ["Dijkstra, add state if needed"]
    G -- "weights may be negative" --> BF["Bellman-Ford"]
    G -- "each node has one outgoing edge" --> BL["Binary lifting"]
    G -- "visit every node or edge once" --> HE["Bitmask DP or Euler tour"]

Most graph problems are won by choosing the right model before writing any code.

Grids as graphs: Labyrinth and Monsters

Labyrinth. A grid has walls, a start A and a goal B. Print a shortest path as letters U, D, L, R. This is breadth-first search, and the only extra work is to remember for each cell how you got there (the previous cell and the move letter), then walk back from the goal and reverse the string. BFS finds the fewest-steps path because it explores by increasing distance.

Monsters. Now some cells hold monsters that all move one step per turn, as you do. You win by reaching a border cell. The trap is trying to simulate the monsters and you at once. The standard fix is two BFS passes:

  1. A multi-source BFS from all monsters at the same time gives monster_time[cell], the earliest turn at which any monster can stand there.
  2. A normal BFS for you, where you may enter a cell only if you arrive strictly earlier than every monster, my_time + 1 < monster_time[next].

If you can reach a border cell this way, nothing can stop you, since a monster cannot be anywhere you stand earlier. The test below compares this with a literal simulation using sets of possible positions on hundreds of random small grids.

Python Labyrinth and Monsters on random grids

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice the habit used in the checks: Labyrinth is validated against Floyd-Warshall on the cell graph (a completely different algorithm), and Monsters against a brute-force simulation. A grader that only compares two BFS programs would share any misunderstanding of the statement.

Negative cycles and a one-time discount

Cycle Finding. A directed graph has edge weights that may be negative. Find a cycle with negative total weight, or say none exists. Use Bellman-Ford: relax all edges n times. Start every distance at 0, which is the same as adding a virtual source with a zero-cost edge to every vertex, so that cycles anywhere in the graph are reachable. If the n-th pass still relaxes an edge, a negative cycle exists. To output it, take the vertex x that was just relaxed and step n times back along the parent array (this guarantees you stand on the cycle), then follow parents until you return to x.

Flight Discount. Find the cheapest route from city 1 to city n when you may use a coupon on one flight, halving its price (rounded down). The idea is to make the state bigger: (city, coupon already used?). Run Dijkstra on these 2n states. From an unused-coupon state you may take an edge at full price, or take it at half price and move to the used layer. An independent check is: the answer is the best of the plain shortest path and dist(1, u) + w / 2 + dist(v, n) over all flights (u, v, w), which the test computes with Floyd-Warshall.

Python Cycle finding and flight discount

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Functional graphs, Hamiltonian paths and Euler tours

Planets Queries (jumps). Every planet has exactly one teleporter to another planet. After k teleports (up to 10^9) from planet x, where are you? A single step table is not enough, but binary lifting is: up[b][v] is where you land after 2^b teleports. Build up[b] from up[b-1] and answer a query by applying the bits of k. This is the same table as in Binary lifting and LCA, and it is the right first tool whenever each node has one outgoing edge.

Hamiltonian Flights. Count the routes from city 1 to city n that visit every city exactly once (n <= 20), modulo 10^9 + 7. The state is (set of visited cities, current city), so ways[mask][last], with transitions to any unvisited neighbor. That is 2^n * n^2 operations. The end city must be reached last, so ignore any state that sits at n with other cities still unvisited. The brute force tries every ordering of the middle cities.

Mail Delivery (Euler circuit). Walk through every edge exactly once and return to the start. An undirected graph has such a circuit exactly when every vertex has even degree and all edges lie in one connected piece. Hierholzer's algorithm builds it: keep a stack of vertices, repeatedly walk along an unused edge pushing vertices, and when stuck, pop the vertex onto the circuit. Implemented with an explicit stack it handles 10^5 edges in Python without recursion. The circuit comes out reversed, which is harmless in an undirected graph. If the finished circuit has fewer than m + 1 vertices, some edges were unreachable, so the answer is "impossible".

Python Planets queries, Hamiltonian flights and Euler circuits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The other graph problems, in one list

  • Counting Rooms, Building Roads, Message Route, Building Teams: flood fill, components and BFS two-coloring.
  • Round Trip and Round Trip II: cycle detection with DFS colors (iterative in Python).
  • Shortest Routes I/II, High Score: Dijkstra, Floyd-Warshall and a Bellman-Ford variant with "longest path" and the check that a positive cycle is reachable and can still reach the end.
  • Game Routes, Course Schedule: topological order, DP on a DAG.
  • Investigation, Cycle Finding: Dijkstra with counts; Bellman-Ford as above.
  • Teleporters Path, Mail Delivery, De Bruijn Sequence: Euler paths and circuits.
  • Planets Cycles, Planets Queries II, Road Reparation, Road Construction: functional graphs, LCA, Kruskal and DSU.
  • Flight Routes Check, Planets and Kingdoms, Giant Pizza, Coin Collector: strongly connected components and 2-SAT, see SCC and 2-SAT for Contests.
  • Download Speed, Police Chase, School Dance, Distinct Routes: flows and matching, see Maximum Flow and Matching.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In Monsters, why run a multi-source BFS from all monsters at once?

    BFS from all monsters simultaneously gives each cell its distance to the nearest monster, which is exactly the earliest arrival time.
  2. 2. How do you make sure you are standing on a negative cycle (not just on a path leading to one) when reconstructing it?

    After n steps back you must have entered a cycle, because a path in the parent graph has at most n - 1 edges before repeating.
  3. 3. What is the state of the Dijkstra in Flight Discount?

    Whether the coupon has been spent changes what future moves cost, so it must be part of the state. This doubles the number of states.
  4. 4. When does an undirected graph have an Euler circuit?

    Every entry into a vertex needs an exit, so degrees must be even; and one walk can only cover one connected piece.

Summary

  • Choose the model first: grid BFS, multi-source BFS, Dijkstra with state, Bellman-Ford, binary lifting, bitmask DP or an Euler tour.
  • Monsters is two BFS passes: monster arrival times, then your strictly-earlier path.
  • Bellman-Ford finds negative cycles; step back n times along parents to land on one before printing it.
  • Adding a flag to the state (coupon used) is the standard way to handle "at most once" rules in shortest paths.
  • Binary lifting answers k-th successor queries in a functional graph; Hierholzer's algorithm builds Euler circuits iteratively.

Next: CSES Range Query and Tree Problems Walkthrough