I have doubt in 3rd part of code where we are finding 0 in matrix and checking the connected components we get on placing 1

#1

how can we do this??? becoz its possible that different components have same number of elements and our current 0 is connected to both of them

#2

hey, use this approach,
in first mark all the regions by their size
suppose
1 1 0
0 0 1
0 0 1
mark it as
2 2 0
0 0 2
0 0 2
these are the size of the ponds also mark them visited while iterating so u do not iterate over the same group again
and using DSU mark the parent of each cell
now iterate over the matrix again
only look for zeroes
once u find a zero
look for the elements adjacent to and pick the value of the elements that have diff parents add them and add 1 to it, to include this zero as well
this will solve your question

#3
#4

this is my code , it is getting tle for some test cases… but giving correct ans for 2 test cases… can you check it?? :frowning:

#5

there are a few errors
first
let’s take this matrix
1 1 0
0 0 0
1 1 0
a fairly simple example
in ur first dfs
map stores
1 -> 2
second time dfs it has to do for (0,1)
it stores 2->2
and the array becomes
1 1 0
0 0 0
2 2 0
up next
u r again trying to solve for each 0 element with a loop, do you see how that is a redundancy?
use this approach, it is same as in the solution, group id is parent, black is 1, white is zero,
https://ide.codingblocks.com/s/77475
it is same as the approach i mentioned in the previous comment