Spotify - Bilateral Projects: Puzzle solution

Correct solution: http://alonso-vidales.blogspot.com.es/2012/05/spotify-bilateral-projects-final-puzzle.html

URL: http://www.spotify.com/es/jobs/tech/bilateral-projects/

The first time that you read this problem you think, hum, is really easy, I can't understand why is classified as the most complex problem. But the real problem is not solve the problem, the question is do it efficient.
The problem consist in a bipartitie graph:
http://en.wikipedia.org/wiki/Bipartite_graph
The bipartitie graphs have some interesting features, the most important to solve the problem is:
In a bipartite graph the maximum cardinality of a matching and the minimum cardinality of a node cover are equal.
Then, we should to find the maximun cardinality and we will have min number of nodes, this reduce a lot the complexity of the problem, we can use the crazy Hopcroft-Karp algorithm:
http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm
Using this algorithm we will obtain the paths for the max cardinality, and at the ends of each path the possible nodes, then we can reduce a bit more the possibilities.
With the possible nodes, we should to iterate over all the permutations of this nodes with the max cardinality as number of nodes.

The solution is:


And I used this third part code for the Hopcroft-Karp algorithm: