Hopcroft-Karp — Maximum Bipartite Matching

BFS builds distance layers, then DFS augments along a maximal set of vertex-disjoint shortest augmenting paths each phase.

Time O(E·√V) Space O(V+E) Phases O(√V)
Slow Fast
Unmatched edge Matched edge BFS layer / explore Augmenting path Free vertex