Appearance
Chapter 6: Advanced Graph Algorithms
Overview
This is where graph problems get serious. Chapter 3 gave you BFS, DFS, and shortest paths — now you'll learn the structural decompositions that power Div 1 C–E solutions. Bridges and SCCs reveal the skeleton of a graph; HLD and centroid decomposition turn tree path queries into segment tree queries; network flow solves matching, assignment, and min-cut problems that seem impossible without it. These are the techniques that separate CF 1700 from CF 2200+.
Navigation
Coming from: Chapter 5 — Strings — string hashing, KMP, suffix arrays, and pattern matching
Going to: Chapter 7 — Mathematics — number theory, combinatorics, and game theory
How This Chapter Is Organized
The topics group into three families. The file numbering reflects this grouping, and the suggested reading order follows it as well.
Connectivity decompositions — Tarjan's DFS exposes the structural skeleton of an arbitrary graph. Bridges and articulation points first; the block-cut tree lifts that information into a tree; SCC condensation does the same for directed graphs and unlocks 2-SAT.
Tree-query decompositions — Once a tree is in front of you, several flattening tricks turn path and subtree queries into array operations. Euler tour gives subtree ranges and LCA via RMQ. HLD handles path-aggregate queries with updates. Centroid decomposition handles "for every pair of nodes" path counting. DSU-on-tree handles offline subtree aggregation. Persistent segment trees give versioned views (often layered with Euler tour). Virtual trees compress queries that touch only a few marked nodes.
Flow and matching reductions — Bipartite matching, max flow / min cut, and min-cost flow are modeling tools. The hard part is recognizing that a problem is a flow problem; the algorithms themselves (Kuhn, Dinic, SSP) are templates.
Topics at a Glance
Connectivity decompositions
| # | Topic | Difficulty | Key Trigger Phrase |
|---|---|---|---|
| 02 | Bridges and Articulation Points | Intermediate | "Which edges/vertices disconnect the graph?" |
| 03 | Block-Cut Tree | Advanced | "Compress biconnected components into a tree" |
| 04 | SCC and 2-SAT | Advanced | "Strongly connected components" or "boolean satisfiability with implications" |
Tree-query decompositions
| # | Topic | Difficulty | Key Trigger Phrase |
|---|---|---|---|
| 01 | Euler Tour and LCA | Intermediate | "Flatten tree for range queries" (subtree sums, path queries) |
| 08 | Centroid Decomposition | Advanced | "Count paths in tree with distance ≤ K" or "tree D&C" |
| 09 | Heavy-Light Decomposition | Advanced | "Path queries on tree with updates" |
| 10 | DSU on Tree | Intermediate | "Subtree aggregation" or "count distinct values in subtree" |
| 11 | Persistent Segment Tree | Advanced | "Kth element in range" or "versioned queries" |
| 12 | Virtual Tree | Advanced | "k special nodes in tree" → compress to O(k) node tree |
Flow and matching reductions
| # | Topic | Difficulty | Key Trigger Phrase |
|---|---|---|---|
| 05 | Bipartite Matching | Advanced | "Maximum matching" or "minimum vertex cover" in bipartite graph |
| 06 | Max Flow / Min Cut | Advanced | "Maximum throughput from source to sink" |
| 07 | Min Cost Max Flow | Advanced | "Flow with minimum total cost" |
If You Only Read 3 Files
- Euler Tour and LCA — because flattening a tree into an array with an Euler tour is the key insight that lets you use segment trees on trees. This technique is a prerequisite for HLD and many tree DP problems.
- Bridges and Articulation Points — because Tarjan's DFS is the gateway to understanding graph connectivity at a structural level. It's also the foundation for SCCs and block-cut trees.
- Centroid Decomposition — because it's the most powerful divide-and-conquer technique for tree problems, turning O(n²) brute force into O(n log n) with a clean recursive structure.
Suggested Reading Order
The file numbering above is the recommended path. Read connectivity decompositions first (02 → 03 → 04), then the tree-query group (01 → 08 → 09 → 10 → 11 → 12), then flow (05 → 06 → 07). If you are coming for a specific contest topic, jump in directly — the only hard prerequisites are noted on each lesson.
Cross-Chapter Connections
- Euler Tour and LCA extends LCA with Binary Lifting from Chapter 3 with range-query-based approaches
- Bridges and Articulation Points builds directly on DFS and Tree DFS from Chapter 3
- Heavy-Light Decomposition requires Segment Tree from Chapter 2
- DSU on Tree relates to Small-to-Large Merging in Chapter 10
- Bipartite Matching extends Bipartite Graphs from Chapter 3
- Max Flow uses BFS for finding augmenting paths (Dinic's algorithm)