Graphs -> Graph Modeling

Before running graph algorithms, decide what the nodes, edges, states, and weights actually represent.

• Topic slug: graphs/graph-modeling
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 4
• Repo companion pages: 2
• Curated external problems: 9

Microtopics

• adjacency-list
• adjacency-matrix
• directed
• undirected
• weighted
• multigraph
• state-graph

Learning Sources

Source	Type
Princeton Graphs	Course
IOI 2025 syllabus PDF	Primary
OI Wiki graph intro	Reference

Practice Sources

Source	Type
CSES Problem Set	Practice
USACO contest archive	Practice

Repo Companion Material

Material	Type
Graph cheatsheet	quick reference
Templates overview	template guide

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Building Roads	CSES	Easy	Components	-	-	Connected Components; Construction; Union-Find	Simple component-based modeling: connect all components with minimum new edges.
Message Route	CSES	Easy	BFS	-	-	Unweighted Graph; Path Reconstruction; Shortest Path	Bare-bones graph modeling for shortest path with a concrete route output.
Third Avenue	AtCoder	Medium	Grid BFS	-	-	Teleporters; Implicit Graph; Grid	A textbook teleporter-state modeling problem on a grid.

2 SAT Modeling

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Giant Pizza	CSES	Medium	2-SAT, SCC	Implication Graph; SCC Condensation; Assignment Extraction	Logical Reductions; Directed Graphs	Implication Graph; Boolean Constraints	A very strong modeling problem: clauses become graph edges and satisfiability becomes SCC.

Coordinate MST

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Built?	AtCoder	Medium	MST, Geometry	Edge Generation By Sorting; DSU; Kruskal	DSU; Sorting; Greedy MST	Coordinate Graph; Kruskal; Sparse Edges	A classic geometry-to-graph reduction before running Kruskal.

Grid Cycle

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Fox And Two Dots	Codeforces	Medium	Grid DFS	DFS With Parent Tracking; Cycle Witness; Component Scan	DFS; Visited States; Parent Pointers	Cycle Detection; Same-Color Regions; Grid Graph	Teaches how to find a cycle in an implicit graph hidden inside a board.

Grid Flood Fill

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Counting Rooms	CSES	Easy	Grid DFS	Iterative DFS; Visited Marking; 4-Neighbor Traversal	Graph Traversal; Stack Or Recursion; Grid Indexing	Flood Fill; Connected Components; Implicit Graph	The cleanest example of turning a matrix into a graph and counting components.

Grid Shortest Path

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Labyrinth	CSES	Easy	Grid BFS	Single-Source BFS; Parent Pointers; Route Recovery	BFS; Parent Tracking; 4-Direction Moves	Shortest Path; Path Reconstruction; Maze; Grid	The standard implicit-grid shortest path with an explicit reconstructed route.

Multi Source BFS

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Monsters	CSES	Medium	Grid BFS	Two-Phase BFS; Distance Grid; Path Reconstruction	Queue BFS; Distance Arrays; Grid Moves	Multi-Source BFS; Escape Path; Timing Constraints; Timing; Escape	A classic hidden-state problem where enemy arrival times change the search space.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
BUILDINGROADS	Building Roads	primary	easy	connected components; component representatives; constructive graph connection	Note	Code
COUNTINGROOMS	Counting Rooms	primary	easy	grid graph modeling; iterative flood fill; connected components	Note	Code
GIANTPIZZA	Giant Pizza	secondary	medium	2-sat; implication graph; assignment extraction	Note	Code
MESSAGEROUTE	Message Route	secondary	easy	breadth-first search; unweighted shortest path; parent reconstruction	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py