## Problem link:

ContestPractice

## 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.