Chapter 13 · Matching
Hopcroft–Karp
Augment along a maximal set of shortest disjoint paths per phase, and the O(E sqrt V) bound falls out of two counting arguments.
#Phases
In one phase: BFS from all free left vertices through alternating edges to compute distances; then DFS-augment along all vertex-disjoint shortest augmenting paths (a maximal set), each of length d = the distance to the nearest free right vertex. Repeat.
#Implementation
int n, m; // |L| = n, |R| = m
vector<vector<int>> g; // g[u] for u in L
vector<int> mt(m, -1), dist(n), ptr(n); // mt[v] = matched left vertex of v in R
bool bfs() {
queue<int> q;
for (int u = 0; u < n; u++) { dist[u] = -1; if (free_left(u)) { dist[u] = 0; q.push(u); } }
bool found = false;
while (q.size()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
int u2 = mt[v];
if (u2 == -1) found = true; // free right vertex at this layer
else if (dist[u2] == -1) { dist[u2] = dist[u] + 1; q.push(u2); }
}
}
return found;
}
bool dfs(int u) {
for (int &i = ptr[u]; i < (int)g[u].size(); i++) {
int v = g[u][i], u2 = mt[v];
if (u2 == -1 || (dist[u2] == dist[u] + 1 && dfs(u2))) { mt[v] = u; return true; }
}
dist[u] = -1; // dead end: prune for this phase
return false;
}
int matching = 0;
while (bfs()) {
fill(ptr.begin(), ptr.end(), 0);
for (int u = 0; u < n; u++) if (free_left(u) && dfs(u)) matching++;
}#The O(E√V) bound
Let M^* be a maximum matching and di the length of the shortest augmenting path after phase i. Then (a) the di are strictly increasing, and (b) after O(√V) phases di > √V, and (c) once d > √V, at most O(√V) further phases are needed. Each phase costs O(E).
(a) After augmenting along a maximal set of shortest paths of length d, no augmenting path of length d remains (else maximality is violated), and no shorter one can appear: the symmetric difference of M and M △ P (for the augmentations performed) shows a new shorter path would have yielded an old one. So distances strictly increase.
(b) Let Mi be the current matching, M^* maximum, d = di > √V. Consider G' = Mi △ M^*: components are even cycles and alternating paths, and there are |M^*| - |Mi| paths that start and end with an M^*-edge — these are augmenting paths for Mi, each of length ≥ d. The paths are vertex-disjoint in M^*-edges… at least they are edge-disjoint, so (|M^*|-|Mi|) · d ≤ |M^*| + |Mi| ≤ 2V, giving |M^*| - |Mi| ≤ 2V/d < 2√V. Each phase increases |Mi| by at least 1, so at most 2√V phases remain.
(c) The same inequality with d ≤ √V bounds the number of early phases by √V since each is a distinct length. Total: O(√V) phases × O(E) per phase. ∎
#What the proof buys the code
The two structural facts the proof needs are exactly the two lines people omit: (i) BFS layers give shortest augmenting paths, so the strict-increase argument holds — a DFS without layers degenerates to Kuhn and loses the bound; (ii) the per-phase ptr cursors plus dist[u] = -1 pruning make the phase O(E) once, not O(VE); without the pruning, dead left vertices get re-searched by every start vertex.
#The bound in numbers
The bound in numbers
- n = m = 105, |E| = 3·105: √V ≈ 450, so ≈ 1.4 × 108 edge visits — a second, fine;
- dense bipartite n = m = 2000: Kuhn's O(VE) = 8×109 fails, HK's 4×106 × 63 ≈ 2.5×108 is borderline, and Hungarian/Dinic may do better in practice;
- random graphs: HK's phases are few (usually 3–6), and greedy-Kuhn is often faster than HK because the BFS/DFS overhead per phase dominates — the classic case where theory and the clock disagree;
- unit networks in general (not just matching): the same O(E√V) argument works for Dinic on any unit-capacity network (Max Flow: Ford–Fulkerson, Dinic, Push–Relabel), which is why "just run Dinic" is asymptotically the same answer here.
#Three bugs specific to this code
free_left(u)must be derived frommt(a left vertex is free iff no right vertex lists it), or maintained in amtLarray — HK with a stale free-list silently under-matches. KeepmtL[u]in sync at both assignments.- In the DFS,
dist[u2] == dist[u] + 1must be tested before the recursive call (layered search), not inside it — otherwise a phase augments along non-shortest paths and the bound is gone (and results stay correct, which is why nobody notices until TLE). - Recursion depth is d ≤ V: for 105-vertex paths-of-length-105 adversarial graphs (a "ladder"), stack overflow; convert the DFS to an explicit stack or precompute with the standard
pthreadtrick (Walks, Trails, Paths, Cycles).
#Where √V shows up elsewhere
The "small/large split" argument is the same as in Small-to-Large Merging (sizes double), in the √V decomposition of a graph into heavy/light vertices, and in the bound "at most 2√V phases remain once paths are long". If you remember it as long augmenting paths ⇒ few of them left, both halves of the proof are automatic.