Finding Augmenting Paths

To find an augmenting path, start from an unmatched vertex $u \in L$ and run a DFS or BFS. Follow these rules: from vertices in $L$, take non-matching edges to $R$. From vertices in $R$, take matching edges back to $L$.

If you reach an unmatched vertex in $R$, you have found an augmenting path. If all unmatched vertices in $L$ fail to find paths, the current matching is maximum. This search takes $O(E)$ time.

Space complexity is $O(V)$ for the data structures used.