School Dance - Algorithm

For each boy $i$ from $1$ to $n$, call $\text{dfs}(i)$ with a fresh visited array. The DFS tries to match boy $i$ to some girl $j$ in his adjacency list. If girl $j$ is currently unmatched, set match[j] = i and return true.

If $j$ is matched to boy $k$, recursively try to rematch $k$ to a different girl. If that succeeds, take $j$ for yourself. Count how many boys successfully match. This count is your answer.

This runs in $O(VE)$ time and uses $O(V)$ space.