Skip to content

Graphs

Core Bridge

Graphs are one of the central contest areas because many problems are really about states and transitions in disguise.

How This Family Splits

This repo treats graphs as four big branches:

  • modeling and traversal: BFS, DFS, shortest paths, MST, SCC
  • trees: subtree structure, LCA, decomposition, and dynamic forests
  • cuts and flow: max-flow, lower bounds, cut trees, and min-cost flow
  • pairing families: matching, assignment, stable marriage, blossom

If you are unsure where a problem belongs, decide the branch first and only then choose the leaf topic.

Use This Area When

  • the clean model is vertices plus edges, even if the story hides that fact
  • you are being asked about reachability, cuts, trees, paths, or pairings
  • the main difficulty is choosing the right graph family, not writing raw loops

Start With One Route

If your bottleneck is... Open first Then
basic modeling and traversals Graph Modeling BFS And DFS, Shortest Paths, Minimum Spanning Tree
tree topics feel fragmented Trees Euler Tour / Subtree Queries, LCA, Heavy-Light Decomposition
cut, flow, and circulation topics feel fragmented Maximum Flow Flow With Lower Bounds, Gomory-Hu Tree, Min-Cost Flow
matching or assignment is the real family Matching Stable Marriage, Hungarian / Assignment Problem, Edmonds Blossom / General Matching

Core Progression

  1. Core first
  2. Graph Modeling
  3. BFS / DFS
  4. Shortest Paths
  5. Minimum Spanning Tree

  6. Topological Sort / SCC

  7. Then add

  8. Bridges / Articulation / BCC
  9. Eulerian Path / Cycle
  10. Trees / Euler Tour / LCA

  11. Two-SAT

  12. Deep later

  13. Virtual Tree / HLD / Centroid Decomposition
  14. Link-Cut Tree / Euler Tour Tree
  15. Maximum Flow / Lower Bounds / Min-Cost Flow
  16. Global Min-Cut / Gomory-Hu
  17. Stable Marriage / Hungarian / Blossom
  18. Tree Isomorphism / De Bruijn Sequence

Good First Repo Anchors

Browse All Subtopics

Go Deeper