I am getting WA in this question -> http://www.spoj.com/problems/IITKWPCI/
Here is my solution -> http://ideone.com/mJsLSq
My algorithm creates an undirected graph having n vertices and positions i,j which are ‘good’ are connected with an edge. Then it finds connected components in this graph, sort data on the positions in each component separately and print out the resulting array. It would be helpful if anyone can give a case on which this algorithm fails, because I have tried many corner cases myself. Thanks in advance
PS: I have assumed we can do multiple swaps between same pair of good positions. For example, if 1,2 is a good position pair, we can swap data at positions 1 and 2 multiple times. Please tell if this assumption is incorrect as well.