SWPERMS - Editorial

ad-hoc
easy
editorial
ipc15p3a
swperm
swperms

#1

Problem link:

Contest
Practice

PROBLEM:

A permutation P= (p[1], p[2], …, p[n]) of (1, 2, …, n) is written on a blackboard. You have m pairs of integers (x_i, y_i). At any stage you can choose a pair (x, y) and swap the values of p[x] and p[y] (note that P is still a permutation after this operation). Initially P= (1, 2, …, n). Find the number of different permutations you can obtain after finite number of operations.


TL;DR:


Consider an undirected graph with vertices 1, 2, …, n where there is an edge between x and y for each given pair (x, y). Let c_1, c_2, \cdots , c_t be the sizes of the connected components of this graph. The answer will be (c_1)!\cdot (c_2)! \cdots (c_t)!


FULL SOLUTION:


Let’s consider the graph where the vertices are labelled 1, 2, …, n and pairs are edges. Note that swapping a pair (x, y) is equivalent to switching the labels of the vertices across the corresponding edge.


Observation 1: If there is no path from u to v in this graph, it is not possible to get a permutation P where P= v.

Proof: Suppose otherwise that it is possible to apply the swaps in some order that the label of vertex u is at the position of vertex v . Let t_1, t_2, ..., t_k be the successive vertices with which u was swapped- this means the edges u-t_1, t_1-t_2, \cdots , t_{k-1}-t_k and t_k-v are all present in our graph, i.e. there is a path from u to v. Contradiction.

From observation 1, we find out that if u and v are in different connected components their positions cannot be interchanged. We can now treat each connected component separately. Let f(i) be the number of ways the i’th component can be permuted, then the answer will be simply f(1) \cdot f(2) \cdots f(t) where t is the number of connected components.

Now we shall prove that all possible permutations of a component can be obtained after finitely many operations, i.e. all k! permutations of a connected component of size k can be attained. Note that this is equivalent to proving that if the graph is connected, all n! permutations are achievable.

Claim: If the graph is connected, all permutations of 1, 2, …, n can be obtained.

Proof: There are probably multiple ways to prove this. Here’s a simple one. We’ll prove that for all u≠v, it is possible to apply the swaps in such a way that the positions of all other elements are unchanged and those of u and v are interchanged. Since the graph is connected, there exists a simple path t_1, t_2, ..., t_k from u to v. Apply the operations u-t_1, t_1-t_2, ...., t_{k-1}-t_k, t_k-v - this brings the label of u to the position of v and the label of v to the position of t_k. Apply the operations t_k-t_{k-1}, t_{k-1}-t_{k-2}, ..., t_1-u again- now all other labels are at their original positions and those of u and v were interchanged. Thus we can always say (u, v) is one of the pairs given to us (even though it isn’t)- because there exists a sequence of allowed operations which has the exact same effect. Now we can simply claim to have all \binom{n}{2} pairs available and it’s easy to get to the conclusion.

This claim shows that the number of permissible permutations of the i’th connected component is (c_i)! where c_i is its size. Thus, the answer is (c_1)! \cdot (c_2) ! \cdots (c_t)! where t is the number of connected components. This can be found in O(m+n) with a plain dfs.