I solved the problem by first checking for a bipartite graph using the input matrix and if the graph was bipartite, I went on to find a way to color it so that the product of the number of vertices in both colors is maximized.

For the latter problem we have pairs (a,b) for each connected component of the bipartite graph representing the number of vertices which should go into each color/side.Now,the problem was to find a division such that the number of vertices are as even as possible.

To solve this first sort on the basis of number of vertices in each component in descending order, and then start filling up the sets such that the greater of a or b always goes into the set which has less vertices.

For eg.

Let the pairs be : (5,1),(3,1),(2,1) (sorted)

Initially the sets are (0,0).

After adding (5,1) → (5,1)

After adding (3,1) → (6,4)

After adding (2,1) → (7,6)

Surprisingly, this solution got accepted but, I could never prove the correctness of this algorithm.

So my question is whether this approach is indeed correct or was the test data for the problem weak ?

Here’s a link to my solution link

**EDIT** : So it is established that the greedy approach is wrong and that the test data was weak. We’ve also got plenty of counter examples and a dynamic programming algorithm in the answers. Thank you @lebron @Amlesh and @thezodiac1994.

Now some one please close the question as I don’t have enough karma to do it