What should i apply dfs or bfs in FIND THE ISLAND Problem? Why?

help
, , , , ,
16

@ssaxena36 yes you are right, but it’s good to know maps too, will be helpful in some other problem. :slight_smile:

2 Likes
17

@ssaxena36 can you please find out the bug in my solution?

Here’s the link : CodeChef: Practical coding for everyone

18

For an entire graph that is connected, suppose has N = 4, You’d do a DFS from node 0 and put count = 1 (1st iteration) while for next iterations of loop from i = 1 to i = 3 visited would be TRUE so there will be no DFS again and count shall remain to 1. In the end, your answer is count - 1 = 0 because all nodes have a path. Hope this simplifies all for you

19

Yes I agree, GPD -MAY17 couldn’t be solved without Maps though. You too had a good point. :slight_smile: btw looking into your solution now.

20

but when i call dfs it will recursively done the dfs,when why i need to call everytime,please dont mind,because this is my first graph problem

21

@vivek96 If you just call the dfs function once then it will only perform dfs in one component of the graph.

If there are more than one components then we will have to iterate and run dfs starting from other vertices too.

1 Like
22

sorry,its not your fault but im unable to understand the concept of components.feeling bad!

23

DFS : to identify a single component.
Re-iteration of the loop : to find out the nodes which are not connected to the previous component found out and search again.

24

@shraeyas Sorry I wasn’t able to figure out the bug but seems like that Map is causing problems. I’m more of a Java/Python user so can’t help much.

25

@ssaxena36 no problem :slight_smile:

26

im getting sigsigv,CodeChef: Practical coding for everyone

27

@vivek96 you have declared the graph wrong.

It should be

vector<vector > graph(2001);

28

but working fine on local.

29

now getting WA.lol

30

Check the for loop you have in your main() function, it should be:

for(int i=1;i<=n;i++)

You missed the equal sign.

31

i corrected the code,but WA is still,u got AC?

32

Not yet :stuck_out_tongue:

33

4 WA…huh

34

now i tried accepted solution,it also gives wa.@admin please look at this matter,i think file issue

35

we all are getting wa.i think file issue