Phase structure
BFS finds all shortest augmenting paths simultaneously. DFS augments along disjoint ones. Repeat.
Advertisement
Why √V phases
After √V phases, augmenting paths have length ≥ √V. But there can be at most √V disjoint such paths. So O(√V) phases.
Advertisement
Complexity
O(E·√V). Each phase O(E). Total √V phases.
Equivalent
Same asymptotic as Dinic's on unit-capacity bipartite flow network.