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

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

2 Answers 2


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.