Practice
Author: Kishore Kumar
DIFFCULTY:
Easy-Medium
EXPLANATION
It is clear that every inversion in the graph (a_i > a_j and i < j) must be resolved by a swap operation to get a sorted array. This means that each of the two dancers in every inversion pair must have different parities/teams. This problem can be solved by constructing the inversion graph and then checking if it is bipartite.
The bug in this problem is that the inversion graph is not necessarily connected. The buggy code only performs a single dfs from node 0 which tries to bipartite color that single component and assigns all unvisited components to team B. The correct solution would involve performing a dfs on every connected component with a minor modification.
Bonus: Changing the code to a simple for loop dfs that performs the given dfs on every connected component alone won’t make the solution hackproof. Can you figure out which case breaks that? 
The buggy would hence fail on cases where the connected component containing node 0 was bipartite but there existed other connected components containing edges that the buggy code would fail to resolve.
4
2 1 4 3
There are two connected components in this test case:
- component 1:
2 1 - component 2:
4 3
We assign a valid bipartite coloring to the first component but assign both nodes 3 and 4 to team B, which gives an invalid solution.