$n$ students want to exchange books among themselves

Question

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

Answer 1

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.

You can probably do this by computing the SCC decomposition and then finding cycles in each connected component.

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.

Answer 2

It seems if you have the same number of people wanting a book and having a book then you can have a swap by everyone putting their book on a pile, then everyone picking the book they want. And if you don’t have the same numbers then you can’t swap.