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

Please tell me how to deal with problems as i am new to graph theory?

3 Likes

Question is simple you need to find total number of connected components.

Connected Component says that in a graph every other node is reachable by any other node following any path in the connected graph.

Just calculate the number of connected components

Suppose there are X connected components.

In the test case mentioned, there are THREE CONNECTED COMPONENTS. Simply, to connect them you’d need X - 1 number of Paths to make each node reachable by other in the entire given graph.

For this you’d need a DFS Approach and start like this

``` count = 0;
for(int i = 0;i < N; i++) // where i represents a node
{
if(!visited[i])
{
{
DFS(i) // where i is source for present DFS logic
count += 1;
}
}
```

Count finally gives you number of connected components, Your answer = count - 1 in every case.

Connected Components

4 Likes

I thought I should post in this new thread.

I am actually printing com-1, so when n==0 then com=1 and com-1 will be printed which will be zero.
So there is some other bug for that WA verdict.

Think of map as an array.

map < type1, type2>mapname;

type1 is the index of that array and type2 is the kind of data stored in that array. So if you write vector in place of type2 then a vector can be stored in an array.

Example of map as an array : map < int,int > ar

ar can be used as a normal array. Also the default value in ar is zero.

2 Likes

why we all are getting Wrong Answers?

I think the tester’s solution is wrong, that’s why we are getting wrong answers
moreover, its editorial has been removed now

1 Like

can any one provide me code to check cycle in graph? @shraeyas

I don’t know why my code is not working. Can anyone check I would be thankful.

example of map as array please

what is ar[0]? im little bit confused due to java working of maps,please clarify

nice explanation…

1 Like

logic behind count=count+1; can u explain?

Initially ar[0] will be equal to zero.

You can put any integer inside it, for example:

int x = 1;
ar[0] = x;

@vivek96 Dont confuse yourself with Maps. Use STL Vectors/ Lists and as you’d asked it on separate question, follow the same pattern.

2 Likes

Whenever you’ve found a disconnected node which is not visited you add a new component by count += 1; Suppose you start the loop at node 0 it will be disconnected as well as go through a possible DFS and mark all other nodes connected to node 0 as Visited. Next iteration would be for a node that is not connected to the initially taken node 0.

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

2 Likes

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