I am getting WA in this question → SPOJ.com - Problem IITKWPCI
Here is my solution → mJsLSq - Online C++0x Compiler & Debugging Tool - Ideone.com
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.