Advanced Graph Algorithms
The residual graph keeps, for every edge, its remaining capacity and a reverse edge holding the flow already sent — pushing flow back along a reverse edge “undoes” an earlier choice.
Eulerian path/circuit and Hierholzer's algorithm.
Hamiltonian path/cycle and exponential complexity.
Bipartite checking and coloring.
Maximum bipartite matching: Kuhn's algorithm and Hopcroft–Karp.
Maximum flow: Ford–Fulkerson, Edmonds–Karp, Dinic.
Minimum cut and max-flow/min-cut theorem.
Min-cost max-flow overview.
Residual graphs and reverse edges.
Network flow applications: matching, assignment, disjoint paths.
2-SAT using implication graphs and SCC.
Tree centers and centroids.
Euler tour technique and subtree flattening.
Lowest common ancestor: binary lifting, Euler tour + RMQ, Tarjan offline LCA.
Rerooting and tree DP.
Virtual trees overview.
Dynamic connectivity overview.
34.1 Maximum flow
The residual graph keeps, for every edge, its remaining capacity and a reverse edge holding the flow already sent — pushing flow back along a reverse edge “undoes” an earlier choice. Ford–Fulkerson augments along any path in the residual graph; Edmonds–Karp always uses a shortest path (BFS), giving O(VE²); Dinic augments along all shortest paths at once using a level graph and blocking flows, O(V²E) in general and much faster on unit-capacity graphs.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The run confirms the max-flow/min-cut theorem: the edges leaving the set of vertices still reachable from the source in the final residual graph have total capacity equal to the maximum flow.
#include <bits/stdc++.h>
using namespace std;
struct Dinic {
struct E { int to; long long cap; };
vector<E> e; vector<vector<int>> g; vector<int> level, it;
explicit Dinic(int n) : g(n), level(n), it(n) {}
void add(int u, int v, long long c) { g[u].push_back((int)e.size()); e.push_back({v, c}); g[v].push_back((int)e.size()); e.push_back({u, 0}); } // edge i and its reverse i^1
bool bfs(int s, int t) {
fill(level.begin(), level.end(), -1); level[s] = 0; queue<int> q; q.push(s);
while (!q.empty()) { int u = q.front(); q.pop(); for (int id : g[u]) if (e[id].cap > 0 && level[e[id].to] < 0) { level[e[id].to] = level[u] + 1; q.push(e[id].to); } }
return level[t] >= 0;
}
long long dfs(int u, int t, long long f) {
if (u == t) return f;
for (int& i = it[u]; i < (int)g[u].size(); ++i) {
int id = g[u][i]; int v = e[id].to;
if (e[id].cap > 0 && level[v] == level[u] + 1) {
long long pushed = dfs(v, t, min(f, e[id].cap));
if (pushed) { e[id].cap -= pushed; e[id ^ 1].cap += pushed; return pushed; }
}
}
return 0;
}
long long maxflow(int
…max flow (Dinic) = 23, Edmonds-Karp = 23
min cut edges: 1->3(12) 4->3(7) 4->5(4) total capacity 23
Dinic matches Edmonds-Karp on 300 random networks34.2 Bipartite graphs and matching
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
A graph is bipartite exactly when it has no odd cycle — the triangle fails. Kuhn's algorithm is O(V·E); Hopcroft–Karp finds many shortest augmenting paths per phase for O(E√V). Matching is also a max-flow problem: source → every left vertex → allowed right vertices → sink, all capacities 1.
#include <bits/stdc++.h>
using namespace std;
int main() {
// bipartite check by BFS 2-coloring
auto bipartite = [](int n, const vector<pair<int, int>>& e) {
vector<vector<int>> adj(n); for (auto [u, v] : e) { adj[u].push_back(v); adj[v].push_back(u); }
vector<int> col(n, -1);
for (int s = 0; s < n; ++s) {
if (col[s] != -1) continue;
col[s] = 0; queue<int> q; q.push(s);
while (!q.empty()) { int u = q.front(); q.pop(); for (int v : adj[u]) { if (col[v] == -1) { col[v] = col[u] ^ 1; q.push(v); } else if (col[v] == col[u]) return false; } }
}
return true;
};
cout << boolalpha << "4-cycle bipartite: " << bipartite(4, {{0, 1}, {1, 2}, {2, 3}, {3, 0}}) << ", triangle bipartite: " << bipartite(3, {{0, 1}, {1, 2}, {2, 0}}) << '\n';
// Kuhn's augmenting-path matching: workers (left) to jobs (right)
vector<vector<int>> can = {{0, 1}, {0}, {1, 2}, {2, 3}};
int L = 4, R = 4;
vector<int> matchR(R, -1);
function<bool(int, vector<bool>&)> tryKuhn = [&](int u, vector<bool>& used) {
for (int v : can[u]) {
if (used[v]) continue;
used[v] = true;
…4-cycle bipartite: true, triangle bipartite: false
maximum matching size: 4 -> worker1-job0 worker0-job1 worker2-job2 worker3-job334.3 Trees: LCA by binary lifting and Euler tours
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Binary lifting precomputes up[k][v], the 2ᵏ-th ancestor, in O(n log n); each LCA query is O(log n). The Euler tour turns every subtree into a contiguous range, so subtree sums and updates become range queries on an array (Fenwick or segment tree).
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 9, LOG = 4;
vector<vector<int>> adj(n);
for (auto [u, v] : vector<pair<int, int>>{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {4, 6}, {4, 7}, {5, 8}}) { adj[u].push_back(v); adj[v].push_back(u); }
vector<vector<int>> up(LOG, vector<int>(n, 0));
vector<int> depth(n, 0), tin(n), tout(n), euler; int timer = 0;
function<void(int, int)> dfs = [&](int u, int p) {
up[0][u] = p; tin[u] = timer++; euler.push_back(u);
for (int v : adj[u]) if (v != p) { depth[v] = depth[u] + 1; dfs(v, u); }
tout[u] = timer; // subtree of u = positions [tin[u], tout[u]) of the Euler order
};
dfs(0, 0);
for (int k = 1; k < LOG; ++k) for (int v = 0; v < n; ++v) up[k][v] = up[k - 1][up[k - 1][v]]; // 2^k-th ancestor
auto lca = [&](int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = LOG - 1; k >= 0; --k) if (depth[a] - (1 << k) >= depth[b]) a = up[k][a]; // lift a to b's depth
if (a == b) return a;
for (int k = LOG - 1; k >= 0; --k) if (up[k][a] != up[k][b]) { a = up[k][a]; b = up[k][b]; }
return
…LCA(6, 7) = 4, distance 2
LCA(6, 3) = 1, distance 3
LCA(8, 7) = 0, distance 6
LCA(4, 6) = 4, distance 1
Euler order: 0 1 3 4 6 7 2 5 8
subtree of 1 is the contiguous slice [1, 6): 1 3 4 6 734.4 2-SAT, Euler paths and the rest
2-SAT: each clause (a ∨ b) becomes implications ¬a → b and ¬b → a. The formula is satisfiable exactly when no variable shares a strongly connected component with its negation; an assignment follows from the SCC topological order. O(n + m).
Eulerian circuit: a connected undirected graph has one when every vertex has even degree (a path when exactly two are odd). Hierholzer's algorithm builds it in O(E) by walking until stuck and splicing in sub-circuits.
Hamiltonian path: visiting every *vertex* once is NP-hard; the bitmask DP of Module 22 solves it in O(n²2ⁿ).
Heavy-light and centroid decomposition: both split a tree so that any path crosses O(log n) pieces, enabling path queries with a segment tree (HLD) or divide-and-conquer over paths (centroid).
Virtual trees compress a tree to the queried vertices and their pairwise LCAs; dynamic connectivity handles edge insertions and deletions, offline with a segment tree over time plus rollback DSU.
Quiz
? Why does every edge in the residual graph have a reverse edge?
+ Pushing flow along the reverse edge cancels earlier flow, so the algorithm can correct bad choices. :: Without it Ford–Fulkerson can get stuck below the maximum.
- To make the graph undirected. :: It stays directed.
- To double the capacity. :: Reverse edges start at 0.
- For printing. :: No.
? The min cut printed by the run had total capacity equal to the max flow. Which theorem is that?
+ Max-flow/min-cut :: The value of a maximum flow equals the capacity of a minimum cut.
- Cut property :: That is about MSTs.
- Master Theorem :: Recurrences.
- Handshake lemma :: Degrees.
? Which statements are true? (select all that apply)
+ A graph is bipartite iff it has no odd cycle :: The triangle failed.
+ Bipartite matching can be solved as max flow with unit capacities :: Source → left → right → sink.
- Finding a Hamiltonian cycle is O(V + E) :: It is NP-hard.
+ An Euler tour makes each subtree a contiguous range :: Subtree queries become range queries.