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

Problem Link-https://www.codechef.com/problems/TRATCK1

Please explain your approach for this problem.

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.

Use this link for Connected Components for more information.
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.

For your second query

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.
CODE LINK: https://www.codechef.com/viewsolution/13936158

example of map as array please

I have added it above

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

nice explanation…:slight_smile:

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. :slight_smile:

2 Likes

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

Here’s the link : https://www.codechef.com/viewsolution/13900283

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

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.

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