Graph Mastery Ladder

What This Ladder Trains: Graph algorithms from basic traversal to advanced structural decomposition. You'll progress through BFS/DFS, connected components, cycle detection, topological sort, shortest paths, DSU, MST, SCC, and network flows. By the end, you should confidently model problems as graphs, choose the right traversal or algorithm, and handle both directed and undirected structures.

Quick Revisit

• SKILL FOCUS: graph mastery -- BFS/DFS through SCC, Dijkstra, and advanced traversals
• DIFFICULTY: 1200--2000
• PROBLEMS: 15
• PREREQUISITE: Graph Foundations

---

Contents

• Warm-Up (1200-1400)
• Core (1400-1600)
• Advanced (1600-1900)
• How to Use This Ladder

---

Warm-Up (≈1200-1500)

BFS/DFS basics, connected components, and simple cycle detection. The tier label is approximate — a few problems sit at 1500 because the modeling step matters more than the algorithm. Don't over-calibrate self-worth from the label.

#	Problem	Rating	Hint
1	Ice Skating	1200	Hint Points sharing an x or y coordinate are connected. Count connected components -- answer is components - 1.
2	Learning Languages	1400	Hint Each person connects the languages they speak via DSU. Answer = components with at least one language - (1 if any person knows a language, else special case).
3	Kefa and Park	1500	Hint DFS from root tracking consecutive cats on path. A leaf is reachable if the count never exceeds m.
4	Fox and Two Dots	1500	Hint DFS with color tracking. A cycle exists if you revisit a visited cell of the same color that isn't your parent.
5	Cthulhu	1500	Hint The graph is "Cthulhu" iff it is connected and has exactly n edges (one cycle). Check both conditions.

If you struggled here, review Chapter 3: Graph Foundations -- BFS, DFS, and connected components.

---

Core (1400-1600)

Topological sort, shortest paths, DSU applications, and bipartite checking.

#	Problem	Rating	Hint
6	Lunar New Year and a Wander	1500	Hint Modified BFS: always expand the smallest unvisited neighbor next. Use a priority queue.
7	Parsa's Humongous Tree	1600	Hint Tree DP: each node takes its min or max value. dp[v][0/1] = max beauty in subtree.
8	Valid BFS?	1700	Hint Sort each adjacency list by position in the given BFS sequence. Then run BFS and compare.
9	Checkposts	1700	Hint Find SCCs (Tarjan/Kosaraju). Each SCC needs one checkpost at its cheapest node. Multiply choices.
10	Graph Without Long Directed Paths	1700	Hint Orient edges so no directed path has length >= 2. This requires bipartiteness -- 2-color and orient accordingly.

If you struggled here, review Chapter 3: Graph Foundations -- topo sort and shortest paths -- and Chapter 6: Advanced Graphs for SCC.

---

Advanced (1600-1900)

DSU with sorting, Dijkstra, 0-1 BFS, and advanced traversals.

#	Problem	Rating	Hint
11	Path Queries	1800	Hint Sort edges by weight and queries by threshold. Process with DSU -- for each component of size s, add s*(s-1)/2 paths.
12	Vasya and a Tree	1800	Hint Euler tour + difference array on depths. For each update, mark +x at depth d and -x at depth d+1 in the DFS.
13	Dijkstra?	1900	Hint Standard Dijkstra with path reconstruction. Watch for the n=1 edge case and use long long for distances.
14	Labyrinth	2000	Hint 0-1 BFS on a grid: going left/right costs 1 unit of the respective budget, going up/down costs 0. Use a deque.
15	Minimal Labels	1900	Hint Reverse all edges and do topological sort greedily assigning the largest label first (using a max-heap). Then reverse the assignment.

If you struggled here, review Chapter 6: Advanced Graphs -- SCC, bridges, and flows -- and Chapter 2: Data Structures for DSU.

---

How to Use This Ladder

1. Draw the graph before coding, and answer the modeling checklist explicitly:

   • Directed or undirected?
   • Weighted or unweighted? (If weighted: integer? non-negative? bounded?)
   • Static or dynamic (edges added/removed over time, possibly offline)?
   • Tree or general graph? (If tree: rooted? where?)
   • Are you computing a path, a connectivity property, or an order property (topo/SCC)?

   Most graph mistakes happen at this step, before the first DFS is written. If you can't answer all five, you don't have the model yet.

2. Time-box: 30 min for Warm-Up, 45 min for Core, 60 min for Advanced.

3. After each problem, identify which graph property made the solution work (connectivity? shortest path? bipartiteness? SCC?).

4. Supplement weak areas. If DSU problems trip you up, solve 3-5 more DSU problems from Codeforces before continuing.

5. Build templates. By the end of this ladder you should have working implementations of: BFS, DFS, Dijkstra, DSU, toposort, SCC (Tarjan or Kosaraju).

Progression Check

• [ ] Warm-Up: solved >= 4/5 without hints
• [ ] Core: solved >= 3/5 within time limits
• [ ] Advanced: attempted all 5, solved >= 2
• [ ] Can implement BFS, DFS, Dijkstra, and DSU from memory in under 10 minutes each
• [ ] Can implement toposort (Kahn's) and one SCC algorithm (Tarjan or Kosaraju) from memory in under 15 minutes each — these come later than the four above, but they are central to the ladder and required before Advanced

---

See also: Graph Foundations | BFS vs DFS Guide | Rating ladders