Help with logic (graph problem)

#1

code : https://ide.codingblocks.com/s/578739

c77d2471-deb4-43c9-a4c0-15de66610fe7.png1861×732

e7209425-ae0d-4de2-a427-0a06da3ac407.png1895×770

I have applied dfs to this problem and made some modifications for this problem but test cases are not passing please help

#2

@raghav007 you are not checking the cells in correct order if your programe return false for one cell from one returns false from one of its dfs then it is not neccesary that the point is in the island if one of the node that complete dfs visits is on the boundry then it is not an island as mentioned in the ques and we need to purn those cases first so first we do a dfs from all the boundry nodes and mark all the nodes reachable as visited and then you do the same process as you are doing …please ask if it is still not clear …and if solved please mark is solved and rate experience…

#3

so what I should do instead run dfs for all the boundary nodes and mark visited then I traverse the graph again and mark all the unvisited nodes as 0 because they are not connected with the ones on the border

#4

yes do dfs from boundry nodes and mark them visited first and then start doing dfs for the remaning nodes as now all those nodes are already visited that are attahed to boundry nodes so if you find an island now mark all those nodes as 0 because they can not be attached to the boundry nodes and must be the island

#6


this code is working in the opposite way it is marking all the nodes as visited please check

#7

@raghav007 you are doing a small mistake if the boundry element is 0 then you are also doing the dfs we do dfs only when the boundry element is equal to 1
Coding Blocks IDE please check this one
and if isssue still exist please ask

#8

thanks a lot it got submitted

#9

@raghav007 please mark it as solved and also rate experience

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.