Valid Pairing of Numbers
List = [3, 0, 2, 1] We have to make ‘0’ adjacent to ‘1’ and ‘2’ to ‘3’. And, to achieve this we can swap ‘0’ with ‘2’. New list = [3, 2, 0, 1]. Therefore, the answer (minimum number of swaps) is equal to 1.
There will be only distinct numbers present in the given list.
The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain a single integer ‘N’ such that the size of the list is 2 * ‘N’. The second line of each test case will contain 2 * ‘N’ integers separated by a single space that represents the elements/numbers present in the list initially.
For each test case, print the minimum number of swaps possible to make every even number ‘E’ adjacent to (‘E’ + 1). Output for every test case will be printed in a separate line.
You don’t need to print anything; It has already been taken care of. Just implement the given function.
1 <= T <= 10 1 <= N <= 100 0 <= ARR[ i ] < 2 * N Time limit: 1 sec
Consider the pair ‘E’ and ‘E’ + 1(where ‘E’ is a particular even number in the given list) as the vertex in the graph. As the size of the given list/array is 2 * ‘N’ and so, the graph will contain ‘N’ vertices. Now, we have to connect the edges between the required vertices. There will be an edge between the two pairs of numbers (two vertices) in the given list if there present ‘E’ in a pair and ‘E’ + 1 in the other or vice-versa.
Now, we have to only find the number of disjoint sets of vertices (number of connected components) in the graph. The answer (minimum number of swaps) will be ‘N’ - the total number of connected components in the graph.
We are going to use an additional function named “FIND” that helps in finding the parent node of a child node. It takes the “PARENT” array and number/vertex ‘X’ as arguments and returns the parent of ‘X’.
int find(vector<int> &parent, int x)
Where “PARENT” is the array that holds all the parent nodes (or we can say root nodes of every connected component present in the graph) and ‘X’ is the vertex whose parent we are trying to find.
The steps are as follows:
Ninja And The Class Room
Distance to a Cycle in Undirected Graph
Ninja And The Strictly Increasing Array