---
title: "Hopcroft–Karp"
summary: Augment along a maximal set of shortest disjoint paths per phase, and the O(E sqrt V) bound falls out of two counting arguments.
difficulty: hard
tags: [matching, bfs, complexity]
time: E sqrt V
space: V + E
prereq: [matching/bipartite]
see: [flow/maxflow, structures/dsu]
---

## Phases

:::definition label="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

```cpp hopcroft-karp.cpp
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\sqrt V)$ bound

:::theorem title="Hopcroft–Karp runs in $O(E\sqrt V)$"
Let $M^*$ be a maximum matching and $d_i$ the length of the shortest augmenting path after phase $i$. Then (a) the $d_i$ are strictly increasing, and (b) after $O(\sqrt V)$ phases $d_i > \sqrt V$, and (c) once $d > \sqrt V$, at most $O(\sqrt V)$ further phases are needed. Each phase costs $O(E)$.
:::

:::proof
(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 \triangle P$ (for the augmentations performed) shows a new shorter path would have yielded an old one. So distances strictly increase.

(b) Let $M_i$ be the current matching, $M^*$ maximum, $d = d_i > \sqrt V$. Consider $G' = M_i \mathrel{\triangle} M^*$: components are even cycles and alternating paths, and there are $|M^*| - |M_i|$ paths that start and end with an $M^*$-edge — these are augmenting paths for $M_i$, each of length $\ge d$. The paths are vertex-disjoint in $M^*$-edges… at least they are edge-disjoint, so $(|M^*|-|M_i|) \cdot d \le |M^*| + |M_i| \le 2V$, giving $|M^*| - |M_i| \le 2V/d < 2\sqrt V$. Each phase increases $|M_i|$ by at least 1, so at most $2\sqrt V$ phases remain.

(c) The same inequality with $d \le \sqrt V$ bounds the number of *early* phases by $\sqrt V$ since each is a distinct length. Total: $O(\sqrt V)$ phases × $O(E)$ per phase. ∎
:::

## What the proof buys the code

:::note title="What to copy from the proof into your 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

:::props title="The bound in numbers"
- $n = m = 10^5$, $|E| = 3\cdot10^5$: $\sqrt V \approx 450$, so $\approx 1.4 \times 10^8$ edge visits — a second, fine;
- dense bipartite $n = m = 2000$: Kuhn's $O(VE) = 8\times10^9$ fails, HK's $4\times10^6 \times 63 \approx 2.5\times10^8$ 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\sqrt V)$ argument works for Dinic on any unit-capacity network (@flow/maxflow), which is why "just run Dinic" is asymptotically the same answer here.
:::

## Three bugs specific to this code

:::warning title="Three bugs specific to this code"
1. `free_left(u)` must be derived from `mt` (a left vertex is free iff no right vertex lists it), or maintained in a `mtL` array — HK with a stale free-list silently under-matches. Keep `mtL[u]` in sync at both assignments.
2. In the DFS, `dist[u2] == dist[u] + 1` must 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).
3. Recursion depth is $d \le V$: for $10^5$-vertex paths-of-length-$10^5$ adversarial graphs (a "ladder"), stack overflow; convert the DFS to an explicit stack or precompute with the standard `pthread` trick (@foundations/walks).
:::

## Where $\sqrt V$ shows up elsewhere

:::example title="Where the sqrt V shows up elsewhere"
The "small/large split" argument is the same as in @advanced-tree/small-to-large (sizes double), in the $\sqrt V$ decomposition of a graph into heavy/light vertices, and in the bound "at most $2\sqrt 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.
:::

:::problems
- [[CSES 1130]] Tree Matching | https://cses.fi/problemset/task/1130 | easy | same objective, and HK is the wrong tool — see why
- [[CSES 1696]] School Dance | https://cses.fi/problemset/task/1696 | core | HK and Kuhn on the same input; time both if you can
:::