πΈοΈ Part 5: Graph Algorithms
Learn to see graphs in problems and solve them efficiently. BFS, DFS, trees, Union-Find, Segment Trees, and Fenwick Trees β the core of USACO Silver.
π 8 Chapters Β· β±οΈ Estimated 3-4 weeks Β· π― Target: Reach USACO Silver level
Part 5: Graph Algorithms
Estimated time: 3β4 weeks
Graphs are everywhere in competitive programming: mazes, networks, family trees, city maps. Part 5 teaches you to see graphs in problems and solve them efficiently. This part also covers tree-based data structures (binary trees, segment trees, Fenwick tree, Union-Find) that are essential for USACO Silver and beyond.
What Topics Are Covered
| Chapter | Topic | The Big Idea |
|---|---|---|
| Chapter 5.1 | Introduction to Graphs | Representing graphs; adjacency lists; types of graphs |
| Chapter 5.2 | BFS & DFS | Traversal, shortest paths, flood fill, connected components |
| Chapter 5.3 | Functional Graphs | Successor graphs, cycle detection, binary lifting |
| Chapter 5.4 | Shortest Paths | Dijkstra, Bellman-Ford, Floyd-Warshall, SPFA |
| Chapter 5.5 | Binary Trees & Tree Algorithms | Tree traversals, LCA, tree diameter, Euler tour |
| Chapter 5.6 | Union-Find (DSU) | Dynamic connectivity, Kruskal's MST |
| Chapter 5.7 | Segment Trees | Range queries and point updates in O(log N) |
| Chapter 5.8 | Fenwick Tree (BIT) | Efficient prefix-sum with point updates |
What You'll Be Able to Solve After This Part
After completing Part 5, you'll be ready to tackle:
-
USACO Bronze:
- Flood fill (count connected regions in a grid)
- Reachability problems (can cow A reach cow B?)
- Simple BFS shortest paths in grids/graphs
-
USACO Silver:
- BFS/DFS on implicit graphs (states rather than explicit nodes)
- Multi-source BFS (distance to nearest obstacle/fire)
- Union-Find for dynamic connectivity
- Graph connectivity under edge additions
- Tree problems (subtree sums, depths, LCA)
- Range queries with segment trees / Fenwick trees
Key Algorithms Introduced
| Technique | Chapter | Time Complexity | USACO Relevance |
|---|---|---|---|
| DFS (recursive & iterative) | 5.2 | O(V + E) | Connectivity, cycle detection |
| BFS | 5.2 | O(V + E) | Shortest path (unweighted) |
| Grid BFS | 5.2 | O(R Γ C) | Maze problems, flood fill |
| Multi-source BFS | 5.2 | O(V + E) | Distance to nearest source |
| Connected components | 5.2 | O(V + E) | Counting disconnected regions |
| Functional graph cycles | 5.3 | O(N) | Successor graph problems |
| Binary lifting | 5.3 | O(N log N) preproc | Walk k steps in O(log k) |
| Tree traversals (pre/post-order) | 5.5 | O(N) | Subtree aggregation |
| LCA (binary lifting) | 5.5 | O(N log N) preproc | Tree path queries |
| Union-Find (DSU) | 5.6 | O(Ξ±(N)) β O(1) | Dynamic connectivity |
| Segment tree | 5.7 | O(log N) | Range queries + point updates |
| Fenwick tree | 5.8 | O(log N) | Prefix sum + point updates |
| Dijkstra's algorithm | 5.4 | O((V + E) log V) | SSSP on non-negative weighted graphs |
| Bellman-Ford | 5.4 | O(V Γ E) | SSSP with negative edges; detect negative cycles |
| Floyd-Warshall | 5.4 | O(VΒ³) | All-pairs shortest paths on small graphs |
| SPFA | 5.4 | O(V Γ E) worst | Practical Bellman-Ford with queue optimization |
Prerequisites
Before starting Part 5, make sure you can:
-
Use
vector<vector<int>>for adjacency lists (Chapters 2.3β3.1) -
Use
queueandstackfrom STL (Chapter 3.1, 3.6) - Work with 2D arrays and grid traversal (Chapter 2.3)
- Understand basic nested loops (Chapter 2.2)
-
Use
priority_queue(Chapter 3.1) β needed for Chapter 5.4 (Dijkstra)
Tips for This Part
- Chapter 5.1 is mostly setup β read it to understand graph representation, but the real algorithms start in Chapter 5.2.
- Chapter 5.2 (BFS) is one of the most important chapters for USACO Silver. Grid BFS appears in roughly 1/3 of Silver problems.
- The
dist[v] == -1pattern for unvisited nodes in BFS is the key. Never mark visited when you pop β always when you push. - Chapter 5.6 (Union-Find) is faster to code than BFS for connectivity questions. Memorize the 15-line template β you'll use it constantly.
- Chapter 5.4 (Dijkstra) is essential for weighted shortest path problems. Use
priority_queue<pair<int,int>>with the standard template. - Chapters 5.7β5.8 (Segment Tree & Fenwick Tree) are crucial for Silver-level range query problems. Fenwick tree is simpler to code; segment tree is more versatile.
π‘ Key Insight: Most USACO graph problems are actually grid problems in disguise. A grid cell (r,c) becomes a graph node; adjacent cells become edges. BFS on this implicit graph finds shortest paths.
π USACO Tip: Whenever you see "shortest path," "minimum steps," or "fewest moves" in a problem, think BFS immediately. Whenever you see "are these connected?" or "how many groups?", think DSU. When you see "range sum" or "range min/max," think Fenwick tree or segment tree.