Construct a graph `G = (V, E)` as follows. The set of vertices, `V`, are the students. If student `A` can give his slot to student `B` to satisfy student `B`, then add the edge `(A,B)` to `E`. We can reduce the problem to one of finding a covering of as many vertices as possible using directed cycles.
We can solve this problem using weighted bipartite matching. The idea is to “match” each student with another student. If student A is matched to student B this mean A gives his slot to B. We want to match a student with another student, if not we match the student to herself. Formally, we construct a weighted bipartite graph `G' = (P, Q, E')` as a follows: The sets of vertices `P` and `Q` are the set of students and for each edge `(a,b)` in `E`, there is an edge `(p_a, q_b)` in `E'` with weight 1. In addition, to model students who do not participate in any swaps, for each student `i` we add an edge `(p_i, q_i)` with weight 0.
The solution is obtained by finding a perfect matching of maximum weight in `G'`. The Hungarian algorithm which runs in `O(n^4)` can be used to solve this problem.