## 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[u]= 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.