Problem set: eighteen graph problems, easy to hard

Why this matters when you build with AI

An AI tool asked for graph code often picks the technique it saw most, not the one the limits require. A weighted shortest-path task gets a plain breadth-first search, which counts edges and ignores weights. A task with 200000 rooms gets an all-pairs table that needs about 8 * 10^15 steps. The code runs and prints a number that looks plausible on a tiny sample.

The fix is an order of work you can check. Read the limits first, name the technique and its cost in one line, and only then write code. Test against a slow method simple enough to trust. None of the problems below names its technique, so you must find it from the statement and the limits.

A prompt that asks for the technique before any code:

Here is a problem statement with its limits. Before writing any code, name the
technique you would use, its time cost, and which simpler technique the limits rule
out and why. Wait for my confirmation, then write the code in C++17.

A good answer names one technique, gives its cost in terms of the limits, and says why a simpler method fails (for example, "BFS counts edges, but the weights differ"). If it starts writing code first, or names a technique too slow for the limits, ask again before you run anything.

How to choose a technique from the limits

Answer these before you read a hint.

How large are the limits? 300 vertices allows n^3 work (27 million steps). 200000 allows about n log n work and rules out n^2.
Are there weights, and what sign? No weights, or equal weights, point to breadth-first search. Weights of 0 and 1 point to a two-ended queue. Non-negative weights point to Dijkstra. Negative weights point to Bellman-Ford, which also finds negative cycles.
Are there many questions on one graph? Build a table or a structure once, then answer each question from it.
Does a choice of edges have to be cheapest, connect everything, or allow undoing the last change? Those words point to spanning trees, a rollback structure, or a reversal.
Do choices imply other choices (if A is on, B must be off)? That is 2-SAT. Does flow move from a source to a sink through capacities? That is a flow problem.

Sums of many values can pass the 32-bit limit (about 2.1 * 10^9), so use 64-bit integers for totals.

How to work through the set

For each problem: write the technique and its cost on paper, read the hint only if still unsure after a minute, write the C++17 code, compile with g++ -std=c++17 -O2, run the sample (it must match exactly), and then write the test named in that problem and run it on at least 300 random small inputs.

The answer keys in this lesson were written in Python, because the samples are small. Each one was checked against its own slow method on 400 random small inputs. Your C++ solutions should match on the samples and on your own random tests.

Worked example: problem 1, end to end

Read problem 1 below first. The code uses a heap (a structure that returns the smallest item first) and lazy deletion: an old entry is left in the heap and skipped when it comes out.

// hallway.cpp: problem 1, shortest time from room 1 to room n.
// Input:  n m, then m lines "u v w" (undirected corridor with time w).
// Output: the shortest time, or -1 if room n cannot be reached.
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, long long>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        long long w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
 
    const long long INF = LLONG_MAX;
    vector<long long> dist(n + 1, INF);
    // Min-heap of (distance, room). Old entries are skipped when popped.
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, v] = pq.top();
        pq.pop();
        if (d > dist[v]) continue;  // a shorter entry for v was already used
        for (auto [u, w] : adj[v]) {
            if (d + w < dist[u]) {
                dist[u] = d + w;
                pq.push({dist[u], u});
            }
        }
    }
    cout << (dist[n] == INF ? -1 : dist[n]) << "\n";
    return 0;
}

Run on the sample of problem 1 (real output):

The best route is room 1, then 3 (1 minute), 2 (2 more), 4 (5 more) and 5 (3 more), a total of 11. I compiled it with g++ 15.2.0 and -std=c++17 -O2, and compared it with Bellman-Ford on 400 random small graphs. There were no mismatches.

The problems

Problems 1 to 3 are easy, 4 to 10 medium, and 11 to 18 hard. The samples are small enough to check by hand, and their outputs come from the answer keys described above.

Problem 1: Hallway walk (easy)

A building has n rooms numbered 1 to n and m corridors. Each corridor joins two rooms and takes w minutes to walk, in either direction. Find the fastest time from room 1 to room n, or print -1 if there is no route.

Input: n and m, then m lines of u, v and w. Limits: n up to 200000, m up to 400000, each w from 1 to 10^9. Hint: a queue visits rooms in order of how many corridors away they are. Your problem counts minutes. Which structure gives back the smallest unfinished time first?

Show the answer

Technique: Dijkstra's algorithm with a binary heap and lazy deletion (the worked example). Complexity: O((n + m) log n). A plain queue counts corridors, not minutes (see the mistakes section). Sample input:

Sample output:

Test to write: Bellman-Ford from room 1 on random graphs with up to 6 rooms, comparing every answer.

Problem 2: Stairs with wall breaks (easy)

A floor plan is a grid of R rows and C columns. A . cell is open and a # cell is a wall. Entering an open cell costs nothing, and entering a wall costs one break. Start at the top-left cell and find the fewest breaks needed to reach the bottom-right cell. The start cell is never charged.

Input: R and C, then R rows of C characters. Limits: R and C up to 1000. Hint: each step costs 0 or 1. Think about a queue that can add to its front for a cost-0 step and to its back for a cost-1 step.

Show the answer

Technique: 0-1 BFS with a double-ended queue. Complexity: O(R * C). Sample input:

3 4
..#.
##.#
...#

Sample output:

Test to write: relax every cell again and again until nothing changes, on random grids up to 5 by 5.

Problem 3: Cable cost (easy)

A city wants to connect n buildings with cables so that every building can reach every other one. Each possible cable joins two buildings and has a price. Find the cheapest set of cables that connects all buildings, or print -1 if that is impossible.

Input: n and m, then m lines of u, v and w. Limits: n and m up to 200000, each w from 1 to 10^9. Hint: a set of cables that connects everything and never makes a loop has exactly n - 1 cables. Which cable should you take first?

Show the answer

Technique: Kruskal's algorithm. Sort the cables by price, add each one that joins two different groups, and track the groups with a disjoint set union. Complexity: O(m log m). Sample input:

Sample output:

Test to write: try every set of n - 1 cables, keep the cheapest that connects everything, on random inputs with up to 5 buildings.

Problem 4: Town distances (medium)

A region has n towns and m two-way roads with lengths. Answer q questions: the shortest distance between towns a and b, or -1 if no route exists.

Input: n, m and q, then m lines of u, v and w, then q lines of a and b. Limits: n up to 300, m up to 3000, q up to 100000, each w up to 10^6. Hint: there are many questions but few towns. What work can be done once, before any question is read?

Show the answer

Technique: Floyd-Warshall fills the table of distances between every pair of towns in n^3 steps, and then each question is a lookup. Complexity: O(n^3 + q). For n = 300 the table is about 27 million steps. Sample input:

Sample output:

8
7
3

Test to write: for each question, run Bellman-Ford from the first town, on random inputs with up to 6 towns.

Problem 5: Dense cable matrix (medium)

There are n sites, at most 2000. The cost of a cable between site i and site j is in an n by n table. The table is symmetric and its diagonal is 0. Find the cheapest set of cables that connects all sites.

Input: n, then n rows of n numbers. Limits: n up to 2000, each off-diagonal cost from 1 to 10^6. Hint: the table already lists every cable. Sorting about n^2 / 2 cables costs more than the question needs. Could you grow one connected piece, always taking the cheapest cable out of it?

Show the answer

Technique: Prim's algorithm on the matrix. For each site not yet connected, keep the cheapest cable to the connected piece, and take the smallest at each step. Complexity: O(n^2), with no sort. Sample input:

Sample output:

Test to write: Kruskal's algorithm on the pairs from the matrix, on random matrices with up to 6 sites.

Problem 6: Cables in some cheapest network (medium)

Use the input format of problem 3. Count the cables that appear in at least one cheapest network that connects all buildings. Print -1 if the buildings cannot all be connected. A cable from a building to itself never counts.

Input: as problem 3. Limits: n and m up to 200000, each w up to 10^9. Hint: many cables may share a price. What happens to a cable whose two ends are already joined by cheaper cables?

Show the answer

Technique: Kruskal's algorithm with each group of equal prices handled together. A cable is in some cheapest network exactly when its ends are not yet joined by strictly cheaper cables. So inside a group of equal price, check every cable before you join any of them. Complexity: O(m log m). Sample input:

Sample output:

Test to write: list every set of n - 1 cables that connects everything, find the cheapest total, and count the cables used by at least one of those sets.

Problem 7: Single points of failure (medium)

A network has n nodes and m links. A link is a single point of failure if removing it splits its piece into more pieces. Count them. Two cables between the same pair of nodes are both safe. The network may already be split.

Input: n and m, then m lines of u and v, with u different from v. Limits: n and m up to 200000. Hint: in a depth-first search, a link to a child is a single point of failure when nothing in the child's part can reach above the parent. Keep for each node the earliest visit time its part can reach.

Show the answer

Technique: depth-first search that records each node's visit time and its low-link value (the earliest visit time reachable from that node's part through one back link). Parallel links are told apart by their number, not by their ends. Complexity: O(n + m). Sample input:

Sample output:

Test to write: remove each link in turn and count the pieces, on random graphs with up to 6 nodes (parallel links allowed).

Problem 8: Family tree ancestors (medium)

A family tree has n people, and person 1 is the oldest ancestor (the root). Each question gives people u and v and a number k. Print the k-th person on the path from u to v, counting u as position 0, or -1 if the path has fewer than k + 1 people.

Input: n and q, then n - 1 lines of two people, then q lines of u, v and k. Limits: n and q up to 200000, k up to n. Hint: one question can walk up one parent at a time, but 200000 walks of up to 200000 steps is too slow. Which jumps can be stored once, and how cheaply can they be combined?

Show the answer

Technique: binary lifting. Store the 2^j-th ancestor of every person for j = 0, 1, 2, and so on. The lowest common ancestor (the first person above both u and v) and the k-th person on the path both come from the jumps. Complexity: O((n + q) log n). Sample input:

Sample output:

4
1
2

Test to write: find the path with a breadth-first search from u, read off the k-th person, on random trees with up to 8 people.

Problem 9: One-way delivery (medium)

A courier starts at room s, must use every one-way street exactly once, and must finish at room t. Print the sequence of rooms, or -1 if no such route exists. Any valid sequence is accepted.

Input: n, m, s and t, then m lines of a and b, a street from a to b. Limits: n and m up to 200000. Hint: a route from s to t becomes a loop if you add one street from t back to s. Which counts must balance for a loop to exist?

Show the answer

Technique: directed Euler circuit. Add the street t to s, check that every room has as many streets leaving as entering, run the iterative Hierholzer algorithm from lesson 13 from s, and cut the loop at the added street. Complexity: O(n + m). Sample input:

Sample output (one valid answer; yours may differ):

3 4 2 3 1 2

Test to write: backtracking over the order of streets, and a validator that checks each step uses an unused street, on random inputs with up to 4 rooms.

Problem 10: Matching and vertex cover (medium)

There are a workers and b jobs (both up to 1000) and e possible pairings (up to 10000). A worker can do a job only if the pairing is listed. Each worker takes at most one job and each job at most one worker. Print two numbers: the largest number of pairs possible, and the smallest number of workers and jobs that together touch every listed pairing.

Input: a, b and e, then e lines of x (a worker) and y (a job). Limits: a and b up to 1000, e up to 10000. Hint: the first number comes from augmenting paths. The second comes from a theorem that links the two numbers. Check it on your sample: are they equal?

Show the answer

Technique: maximum bipartite matching by augmenting paths (Kuhn's method, or Hopcroft-Karp for larger inputs). The second number comes from König's theorem: a search from the unmatched workers, after the matching, gives a cover of the same size. Complexity: O(V * E) for Kuhn, O(E * sqrt(V)) for Hopcroft-Karp. Both are fast enough here. Sample input:

Sample output:

2 2

Test to write: try every subset of pairings for the matching size, and every subset of workers and jobs for the cover, on random inputs with up to 4 workers and jobs.

Problem 11: Price drift (hard)

A network of markets has n markets and m one-way trades. A trade from a to b costs w, and a negative cost is a gain. Find the lowest total cost of a route from market s to market t. Print UNREACHABLE if t cannot be reached. Print -INF if a cycle of trades with a negative total can be reached from s and can reach t, because then the route can go round that cycle as often as it likes.

Input: n, m, s and t, then m lines of u, v and w. Limits: n up to 500, m up to 2000, each w from -10^4 to 10^4. Hint: negative costs break the rule that the first arrival is the cheapest. How many trades can the cheapest route have if no cycle is negative? What does a trade that still improves after that many rounds tell you?

Show the answer

Technique: Bellman-Ford. Relax every edge in n - 1 rounds. An edge that can still be relaxed after that points to a market on or after a negative cycle. Spread that mark forward along the edges, and check whether t gets it. Complexity: O(n * m). Sample input:

Sample output:

-INF

Test to write: Floyd-Warshall with a check that the distance from a market to itself is negative, on random graphs with up to 5 markets.

Problem 12: Undo the merges (hard)

There are n teams, starting with one person each (1 to n). The operations are: M a b merges the team of a with the team of b; U undoes the most recent merge still in effect (it does nothing if there is none); Q a b prints YES if a and b are in the same team now, and NO otherwise.

Input: n and q, then q operations, one per line. Limits: n and q up to 200000. Hint: a structure that merges quickly often cannot split again. What must each merge remember so that merges can be reversed, last one first?

Show the answer

Technique: a disjoint set union with union by size and no path compression, plus a stack of changes. Each merge pushes the one link it made (or nothing, if the two were already together). U pops the stack and reverses that link. Complexity: O(log n) per operation, because without path compression the tree depth stays logarithmic. Sample input:

Sample output:

YES
YES
NO

Test to write: keep the list of merges still in effect, answer each question by a breadth-first search over that list, on random operation lists with up to 6 people.

Problem 13: Make it strong (hard)

A directed network has n rooms and m one-way streets. Print the fewest new one-way streets to add so that from every room you can reach every other room. Print 0 if no streets are needed.

Input: n and m, then m lines of a and b, a street from a to b. Limits: n and m up to 200000. Hint: first group the rooms that reach each other in both directions. Then count the groups that receive no street from another group, and the groups that send none. How many new streets join those groups together?

Show the answer

Technique: strongly connected components (Kosaraju's or Tarjan's method). Count the components with no street from another component into them (sources) and those with none out (sinks). If there is one component the answer is 0. Otherwise it is the larger of the two counts. Eswaran and Tarjan (1976) studied this augmentation problem. I did not read that paper in full, and I checked the count only on random small graphs. Complexity: O(n + m). Sample input:

Sample output:

Test to write: add every set of k new streets, for k = 1 upward, until the network is strong, on random inputs with up to 4 rooms.

Problem 14: Chains of groups (hard)

A project has n tasks, and task i takes w_i days. Each dependency a b means task a must be done before task b. Tasks that depend on each other in a loop form one group, which costs the sum of its days. Find the largest total cost of a chain of groups, where each group comes before the next in the chain.

Input: n and m, then a line of n durations, then m lines of a and b. Limits: n and m up to 200000, each duration from 1 to 10^9. Hint: find the groups first, as in problem 13. The groups then form a graph with no loops, so you can compute the best total ending at each group in a suitable order.

Show the answer

Technique: strongly connected components, then a longest path on the graph of groups. Process the groups in topological order (every group after the groups before it), and let each group's best total be its own cost plus the largest best total of a group before it. Complexity: O(n + m). Sample input:

Sample output:

Test to write: find the groups from the mutual reachability table, then find the longest chain by a memoised recursion, on random inputs with up to 6 tasks.

Problem 15: Shift scheduling (hard)

There are n people, and each works shift 0 or shift 1. Each rule says: person a has shift sa, or person b has shift sb (sa and sb are 0 or 1). Print IMPOSSIBLE if no assignment obeys every rule. Otherwise print one shift per person, separated by spaces. Any valid assignment is accepted.

Input: n and m, then m lines of a, sa, b and sb. Limits: n up to 200000, m up to 400000. Hint: give each person two nodes, one for shift 1 and one for shift 0. Each rule says that if one choice is refused, the other must be taken, which gives two arrows. When can a person's two nodes be on a cycle together?

Show the answer

Technique: 2-SAT. Build the implication graph on 2n nodes and find its strongly connected components. Answer IMPOSSIBLE if a person's two nodes share a component. Otherwise choose each person's shift from the order of their components in topological order. Complexity: O(n + m). Sample input:

Sample output (one valid answer; yours may differ):

1 0 1

Second sample input, with no valid assignment:

1 2
1 1 1 1
1 0 1 0

Second sample output:

IMPOSSIBLE

Test to write: a checker that verifies each rule for your assignment, and a brute force over all 2^n assignments for the IMPOSSIBLE answers, on random inputs with up to 5 people.

Problem 16: Pipe capacity (hard)

A water network has n junctions and m directed pipes. Each pipe carries at most c litres per minute. Find the largest flow from junction s to junction t.

Input: n, m, s and t, then m lines of a, b and c. Limits: n up to 5000, m up to 50000, each c up to 10^9. Hint: flow sent along a pipe can be undone later if another path needs the room. Each pipe needs a reverse copy for that. Which search finds the shortest augmenting paths first, and how many rounds does it need?

Show the answer

Technique: maximum flow by Dinic's algorithm on the residual graph. Each round builds a level graph by breadth-first search, then sends a blocking flow, with a pointer per node that moves past dead ends. Complexity: O(V^2 * E) in the worst case, and usually much faster. Sample input:

Sample output:

Test to write: Edmonds-Karp (augmenting paths found by breadth-first search on a matrix of capacities), on random inputs with up to 6 junctions.

Problem 17: Farthest cafe (hard)

A tree of n junctions has roads with lengths w of at least 1. Some junctions have a cafe. For every junction v, print the distance to the farthest cafe (a cafe at v counts, at distance 0). Print -1 for every junction if there is no cafe.

Input: n, then n - 1 lines of u, v and w, then n flags (1 for a cafe, 0 for none) for junctions 1 to n. Limits: n up to 200000, each w from 1 to 10^9. Hint: root the tree at junction 1. First find, for each junction, the farthest cafe below it. Then pass a value down from each parent to each child. The parent needs its best two child values, so that it can leave out one child.

Show the answer

Technique: rerooting dynamic programming. A pass from the leaves up gives the best distance to a cafe below each junction. A pass from the root down gives the best distance going up through the parent, leaving out the child's own branch. Complexity: O(n). Sample input:

Sample output:

5 2 3 2

Test to write: a depth-first search from each junction over the whole tree, taking the largest distance to a cafe, on random trees with up to 7 junctions.

Problem 18: Corridor paint (hard)

A tree has n rooms, and each room holds a number. The operations are: 1 u v x adds x to every room on the path from u to v (both ends included), and 2 u v prints the total of the numbers on that path.

Input: n and q, then n - 1 lines of two rooms, then a line of n starting values, then q operations. Limits: n and q up to 200000, each value and x up to 10^9 in size. Totals need 64-bit integers. Hint: a tree path can be cut into a few pieces, and each piece can be a range of positions in an array. Which structure answers range sums and range additions in logarithmic time?

Show the answer

Technique: heavy-light decomposition, which gives each chain a range of positions, plus a segment tree with lazy addition (an addition is stored at a node and passed down only when a child is needed). A path becomes a few range operations. Complexity: O(log^2 n) per operation. A walk along the path costs O(n) per operation, too slow for 200000 operations. Sample input:

Sample output:

18
3

Test to write: walk the path from u to v one room at a time (after a breadth-first search for the parents), on random trees with up to 7 rooms and random operations.

Common mistakes in choosing a technique

Both mistakes below were run on the samples of this set, and the outputs are real.

Plain breadth-first search on a weighted graph. On the sample of problem 1, a queue that counts corridors reaches room 5 in 3 steps and prints 3. The correct answer is 11. The symptom is an answer that counts edges, not minutes. Ignoring the weights is the sign of the wrong technique.
Marking a vertex as finished when it is popped, with a negative edge. Take start 1, with an edge 1 to a costing 1, 1 to b costing 2, b to a costing -2, and a to t costing 1. The version that skips finished vertices printed a = 0 and t = 2. The correct value for t is 1, through b and a. The symptom is a wrong answer that still looks plausible. Use Bellman-Ford, as in problem 11.

Two more mistakes come up in this set. Floyd-Warshall at the limits of problem 5 (2000 sites), or on 200000 rooms, needs far too many steps. A recursive depth-first search over 200000 rooms can overflow the stack, as lesson 13 showed; use an explicit stack.

Checklist to keep

Name the technique and its cost from the limits before you code.
Check the sign of the weights before you choose a shortest-path method.
Use 64-bit integers for totals.
Run the sample first. It must match the sample output exactly.
Run the test named in each problem on at least 300 random small inputs.
If the problem accepts any valid answer, write a checker and test with it, not with a string comparison.

Summary

The limits and the statement choose the technique. Weights choose the shortest-path method, cost rules choose the spanning tree, the shape of a tree choose the range method, and what must be undone or implied chooses the rest. A correct sample is not enough. Each problem's test is a slow method you trust, run on many random small inputs.

What is known and what I checked

Known: the techniques named here are standard, and their sources are in lessons 1 to 13 of this module.
Checked: all eighteen answer keys were written in Python and run on 400 random small inputs each, against an independent slow method (for problems 9 and 15, a validator plus a brute-force search). The problem 1 C++ solution was compiled with g++ 15.2.0 with -std=c++17 -O2, and matched the slow method on 400 random graphs. The sample outputs in this lesson come from these runs.
Not checked: the speed of the answer keys at the largest limits. The complexities count steps and are not measurements. For problem 13, the count is checked only on small graphs.