EP Ethan Pham Project Euler, competitive programming, and notes on the things I keep studying.
Data Structures & Algorithms

Graph Algorithms

When a problem hides an interaction graph, these notes aim to make the graph structure explicit instead of magical.

12 published notes
4 planned topics
4 advanced or expert notes
basic starting level
Back to DSA Competitive Programming
Category Overview

Graph Algorithms

Traversal, shortest paths, tree decompositions, and structure-finding routines.

Raw TeX

Overview

Graph problems often become simpler once the hidden graph is made explicit. The notes here focus on that step: identify the graph, identify the query pattern, then choose the graph routine that preserves the structure you care about.

What I Care About in This Category

The most reusable graph ideas are usually not the proofs in isolation but the reductions:

  • when a shortest-path routine is enough and when it is not,

  • when a tree should be linearized,

  • when the hard part is actually the path aggregation structure around the graph.

Difficulty Bands

How this branch is distributed

The labels are not cosmetic. They are there to signal the amount of prerequisite structure and implementation fragility you should expect before opening the note.

basic: 2 intermediate: 6 advanced: 4 expert: 0
2 basic
basic

These are the shortest on-ramp notes in this category and the ones most likely to be usable immediately in contest practice.

BFS and DFS, Topological Sort

6 intermediate
intermediate

These notes assume the base routine is already familiar and focus on the first real structural upgrades.

Dijkstra, Minimum Spanning Tree, Euler Tour Technique, Lowest Common Ancestor (Binary Lifting), Strongly Connected Components, Bridges and Articulation Points

4 advanced
advanced

These are the notes where proofs, reductions, or implementation details become the main bottleneck.

2-SAT, Virtual Tree, Centroid Decomposition, Heavy-Light Decomposition

Published notes

What is already written

These are the finished note pages in this category, each with rendered TeX, C++ code, references, and practice suggestions.

01
basic

BFS and DFS

The fundamental graph traversals for reachability, layering, component discovery, and tree exploration.

graph traversal reachability / components
02
intermediate

Dijkstra

Single-source shortest paths in non-negative weighted graphs with a min-heap and lazy deletions.

shortest paths graphs / priority queue
03
basic

Topological Sort

Order a DAG so every directed edge points forward, then reuse that order for dependency processing and DAG DP.

DAG ordering / dependencies
04
intermediate

Minimum Spanning Tree

Connect a weighted graph as cheaply as possible, usually with Kruskal and DSU as the contest default.

weighted graphs Kruskal / DSU
05
intermediate

Euler Tour Technique

Flatten a rooted tree into entry and exit times so subtree queries become interval queries on an array.

trees flattening / subtree queries
06
intermediate

Lowest Common Ancestor (Binary Lifting)

Lift nodes by powers of two so LCA and ancestor queries become logarithmic after one tree preprocessing pass.

trees binary lifting / ancestor queries
07
intermediate

Strongly Connected Components

Compress a directed graph into its mutually reachable blocks, then reason on the resulting DAG instead of the original cycles.

directed graphs SCC / condensation DAG
08
intermediate

Bridges and Articulation Points

Use DFS lowlink values to find edges or vertices whose removal disconnects an undirected graph.

lowlink graph structure / connectivity
09
advanced

2-SAT

Reduce two-literal clauses to an implication graph, then solve satisfiability with SCC decomposition.

logic SCC / implication graph
010
advanced

Virtual Tree

Compress a query's marked nodes and the LCAs between them into a much smaller tree that preserves the relevant paths.

tree queries lca / compression
011
advanced

Centroid Decomposition

Recursively split a tree by balanced centroids so global path problems can be reduced to logarithmically many local views.

trees divide and conquer / path queries
012
advanced

Heavy-Light Decomposition

Reduce tree path queries to a logarithmic number of segment queries by carving the tree into heavy chains.

trees path queries / segment tree
Study Order

Recommended order to read this branch

The default order follows each note's dependency weight: early notes establish primitives, later notes reuse them or assume the same invariants without re-explaining them.

01
basic

BFS and DFS

The fundamental graph traversals for reachability, layering, component discovery, and tree exploration.

graph traversal reachability / components
02
intermediate

Dijkstra

Single-source shortest paths in non-negative weighted graphs with a min-heap and lazy deletions.

shortest paths graphs / priority queue
03
basic

Topological Sort

Order a DAG so every directed edge points forward, then reuse that order for dependency processing and DAG DP.

DAG ordering / dependencies
04
intermediate

Minimum Spanning Tree

Connect a weighted graph as cheaply as possible, usually with Kruskal and DSU as the contest default.

weighted graphs Kruskal / DSU
05
intermediate

Euler Tour Technique

Flatten a rooted tree into entry and exit times so subtree queries become interval queries on an array.

trees flattening / subtree queries
06
intermediate

Lowest Common Ancestor (Binary Lifting)

Lift nodes by powers of two so LCA and ancestor queries become logarithmic after one tree preprocessing pass.

trees binary lifting / ancestor queries
07
intermediate

Strongly Connected Components

Compress a directed graph into its mutually reachable blocks, then reason on the resulting DAG instead of the original cycles.

directed graphs SCC / condensation DAG
08
intermediate

Bridges and Articulation Points

Use DFS lowlink values to find edges or vertices whose removal disconnects an undirected graph.

lowlink graph structure / connectivity
09
advanced

2-SAT

Reduce two-literal clauses to an implication graph, then solve satisfiability with SCC decomposition.

logic SCC / implication graph
010
advanced

Virtual Tree

Compress a query's marked nodes and the LCAs between them into a much smaller tree that preserves the relevant paths.

tree queries lca / compression
011
advanced

Centroid Decomposition

Recursively split a tree by balanced centroids so global path problems can be reduced to logarithmically many local views.

trees divide and conquer / path queries
012
advanced

Heavy-Light Decomposition

Reduce tree path queries to a logarithmic number of segment queries by carving the tree into heavy chains.

trees path queries / segment tree
Planned topics

Next topics in this branch

These are still intentionally shown as planned or outline topics rather than shallow filler. The branch should feel incomplete in honest places instead of fake-complete everywhere.

Bellman-Ford planned Floyd-Warshall planned DSU on tree planned Dominator tree outline
Resources

Source Files and Assets

Raw files are still available here when you want the original TeX, C++, or statement assets.

Show raw files
Category TeX sourcecompetitive_programming/dsa/graph-algorithms/index.tex