Hopcroft–Karp algorithm

Remarks

Example: let $U = \set{u_1, u_2}$ and $W = \set{w_1, w_2}$ with edges $u_1 w_1$, $u_2 w_1$ and $u_2 w_2$. In the first phase $\ell = 1$, and a maximal set of disjoint single edges is $\set{u_1 w_1, u_2 w_2}$, which is already a perfect matching. If instead the first phase chooses $\set{u_2 w_1}$, the second phase uses the augmenting path $u_1, w_1, u_2, w_2$ of length $3$ and gives the same size $2$.

Non-example: the path $u_1, w_1$ is not augmenting for $M = \set{u_2 w_1}$, because $w_1$ is not free.

By Berge's theorem, a matching is maximum if and only if it has no augmenting path, so the output is a maximum matching. Step 2 uses breadth-first search and step 3 uses depth-first search, so each phase takes time $O(m)$. There are $O(\sqrt{n})$ phases, so the total time is $O(m \sqrt{n})$, where $n$ is the number of vertices and $m$ the number of edges.