Either find a perfect matching, or return a witness that none exist
I would use a degenerated version of the Hungarian algorithm (O(n^3)).

In the basic version on a U, V bipartite graph, you loop on the elements of x of U to give them the best assignement y from V. if y is already assigned, you make a growing subset X of U that may change their affectation without regret until:


either X has at least |X| neighboors in V => then you move your assignements to add properly x.
either X cannot grow anymore without regret and you accept to modify the weights (as the regret cannot be prevented).


For your problem, there is no weight. So if you are in the second case, just break off and you have your X subset. Else you will reach the last x of U and have a perfect assignement.