# $n$ students want to exchange books among themselves

This is a problem from my Algorithms course in uni

There are $$n$$ students, each have a single book. They come into a party to exchange books among themselves. Each have a list of students that have the book that they want.

Give and prove an algorithm that says if a switch of books is possible, i.e. every student got the book that they want.

*A student can't write themself in their list

**If student $$i$$ took student $$j$$'s book, it doesn't mean that student $$j$$ also took student $$i$$'s book

My algorithm is as follows: Go over the lists from shortest to longest (if there are several lists of same size, start with the list that belongs to biggest number, and progress in ascending order): In the list $$i$$, take the minimal student's number which isn't marked taken, and mark it as taken. If there is none, return with false

When you're done, return with true

I didn't manage to prove it, so I don't even know if it's true. Thanks in advance

• With an appropriate bipartite graph, this can be solved with maximum cardinality matching Mar 8 at 17:57
• @Suspicious_1 Are you interested in a better answer? If you have understood Matthews comment, I would encourage you to write an answer. Mar 12 at 18:30

If you reformulate this problem as a graph problem with students as the vertices and directed edge from $$i$$ to $$j$$ when $$i$$ wants $$j$$'s book, then this problem translates to finding a sub-graph over all vertices which is a union of simple directed cycles.
Also, here's an example with 6 students for which your algorithm doesn't work. $$1: \{2,3\}, 2: \{4,5,6\}, 3: \{1,5,6\}, 4: \{2,5,6\}, 5: \{2,4,6\}, 6: \{2,4,5\}$$. A solution would be the decomposition into cycles $$(1,3)$$ and $$(2,4,5,6)$$ but your algorithm makes the wrong choice for $$1$$ in the first step itself.